遍历的迭代实现

为什么需要迭代遍历？

• 动机: 递归深度受调用栈限制, 深树可能栈溢出;
• 手段: 用显式栈模拟递归的入栈与回溯过程;

前序遍历的栈实现怎么写？

• 思路: 一路向左入栈并访问, 无左子节点时出栈并转向右子节点;
• 循环条件: 当前节点非空或栈非空都要继续;

const preorderTraversal = (root) => {
  const res = [];
  const stack = [];
  let node = root;
  while (node != null || stack.length !== 0) {
    while (node != null) {
      res.push(node.val);
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    node = node.right;
  }
  return res;
};

中序遍历的栈实现怎么写？

• 与前序的唯一差别: 访问时机移到出栈之后, 而不是入栈时;

const inorderTraversal = (root) => {
  const res = [];
  const stack = [];
  let node = root;
  while (node != null || stack.length !== 0) {
    while (node != null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    res.push(node.val);
    node = node.right;
  }
  return res;
};

后序遍历如何复用前序代码？

• 观察: 前序为 根-左-右; 把左右访问次序对调得到 根-右-左; 该序列整体倒序就是 左-右-根;
• 实现: 按 根-右-左 入栈访问, 最后 reverse();

const postorderTraversal = (root) => {
  const res = [];
  const stack = [];
  let node = root;
  while (node != null || stack.length !== 0) {
    while (node != null) {
      res.push(node.val);
      stack.push(node);
      node = node.right;
    }
    node = stack.pop();
    node = node.left;
  }
  return res.reverse();
};

• 复杂度: 三种迭代写法都是时间 O(n), 空间 O(h), h 为树高;
• 适用: 迭代写法便于在中途提前返回, 也用于第 k 小这类按序停下的问题, 见 第K小与第K大元素;