二叉树先中后序遍历：递归与非递归实现

什么是二叉树

树中每个节点最多只能有两个子节点
在 Js 中通常用 Object 来模拟二叉树

因为最多两个孩子，所以不用 children 数组，直接用 left 和 right 两个具名字段，空的地方写 null。这个约定让代码里可以直接写 root.left，比操作数组下标清楚。

下图是一棵二叉树的结构示意，下面所有代码用的就是这棵树。

先中后序这三种遍历，本质上是同一个递归过程，区别只有一处：访问根节点这个动作，放在处理左右子树之前、中间、还是之后。「先中后」这三个字说的就是根节点的位置，左子树永远在右子树之前。想清楚这一点，三段递归代码其实是同一段代码，只是那行 console.log 挪了位置。

先序遍历

访问根节点
对根节点的左子树进行先序遍历
对根节点的右子树进行先序遍历

先序的特点是根节点最先被访问，所以输出序列的第一个元素一定是根。这个性质在「根据遍历序列重建二叉树」这类题里是关键突破口——拿到先序序列就等于拿到了根，再配合中序序列切分出左右子树的范围，就能递归还原整棵树。

以下为遍历的测试数据

这棵树的形状是：根为 1，左子树根为 2（孩子 4、5），右子树根为 3（孩子 6、7）。是一棵满二叉树，方便对照三种遍历的输出差异。

const bt = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null,
    },
    right: {
      val: 5,
      left: null,
      right: null,
    },
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: {
      val: 7,
      left: null,
      right: null,
    },
  },
};

递归版几乎是把上面那三句口诀直译过来。开头那个 if (!root) return 是递归的终止条件，也顺手处理了传入空树的情况——因为叶子节点的 left 和 right 是 null，递归调用会走到这里返回。

这棵树的先序输出是 1、2、4、5、3、6、7。

const preorder = root => {
  if (!root) {
    return;
  }
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
};

preorder(bt);

非递归版

递归好写，但递归深度受调用栈限制，树退化成链表时可能溢出。非递归版用一个显式的数组当栈，把调用栈的工作接管过来。

这里有一处很容易写错的地方，也是这段代码最值得注意的点：入栈顺序是先右后左。栈是后进先出，先压右孩子、后压左孩子，弹出时左孩子才会先出来，从而保证「左子树先于右子树」。如果按直觉先压左再压右，输出就变成先右后左了。

const preorder = root => {
  if (!root) {
    return;
  }
  const stack = [root];
  while (stack.length) {
    const n = stack.pop();
    console.log(n.val);
    if (n.right) stack.push(n.right);
    if (n.left) stack.push(n.left);
  }
};

preorder(bt);

中序遍历

对根节点的左子树进行中序遍历
访问根节点
对根节点的右子树进行中序遍历

中序是三者里应用最特殊的一个，因为它有个很强的性质：对二叉搜索树做中序遍历，输出的结果是有序的。二叉搜索树的定义是左子树所有值小于根、右子树所有值大于根，而中序恰好按「左、根、右」的顺序输出，所以自然升序。判断一棵树是不是合法的二叉搜索树，最简单的思路就是中序遍历一遍看结果是否严格递增。

递归版只是把 console.log 从三行的最前面挪到了中间，其余一模一样。这棵树的中序输出是 4、2、5、1、6、3、7，可以看到根节点 1 落在了正中间，左子树的三个节点在它前面。

const inorder = root => {
  if (!root) {
    return;
  }
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
};

inorder(bt);

非递归版

中序的非递归版是三个里面最不好想的，因为访问根节点的时机被夹在中间：走到一个节点时不能立刻访问它，得先把它整条左边界压进栈，等左边处理完了再回来访问。

代码的结构是内外两层循环。内层那个 while (p) 干的是「沿着左指针一路往下，把经过的节点全压进栈」，走到最左下角为止。然后弹出栈顶访问它——此时它的左子树已经确定为空或者已处理完，所以可以安全访问。访问后把 p 指向它的右孩子，外层循环继续，对右子树重复同样的过程。

外层的循环条件 p || stack.length 两个条件都不能少。p 非空表示还有子树没下探，stack.length 非零表示还有节点压着等待访问。只判断其中一个都会提前退出：刚弹出一个叶子节点时 p 会变成 null，但栈里还有它的祖先没访问。

const inorder = root => {
  if (!root) {
    return;
  }
  const stack = [];
  let p = root;

  while (p || stack.length) {
    // 首先把 root 塞到 stack 中, 然后把 left 都塞到 stack 中
    while (p) {
      stack.push(p);
      p = p.left;
    }
    // 逐步删除 root left
    const n = stack.pop();
    console.log(n.val);
    p = n.right;
  }
};

inorder(bt);

后序遍历

对根节点的左子树进行后序遍历
对根节点的右子树进行后序遍历
访问根节点

后序的性质是根节点最后被访问，也就是说处理某个节点时，它的两棵子树都已经处理完毕。凡是「父节点的结果需要依赖子节点的结果」的场景，都得用后序：计算树的高度、统计每棵子树的节点数、判断是否平衡、以及释放整棵树的内存——必须先释放孩子再释放自己，否则孩子的引用就丢了。

递归版是把 console.log 挪到了最后。这棵树的后序输出是 4、5、2、6、7、3、1，根节点 1 排在末尾。

const postorder = root => {
  if (!root) {
    return;
  }
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
};

postorder(bt);

非递归版

这个实现用了一个很巧的思路，不是硬去模拟后序的访问时机，而是绕了一圈。

关键观察是：后序是「左、右、根」，把它整个反转过来就是「根、右、左」。而「根、右、左」跟先序的「根、左、右」只差左右孩子的顺序。所以做法变成两步：先按「根、右、左」的顺序遍历一遍，把结果攒起来，最后整体反转输出。

对照代码看：stack 那部分和先序的非递归版结构完全一样，只是入栈顺序改成了先左后右，于是弹出时右孩子先出，得到「根、右、左」的顺序。但这些节点不直接打印，而是推进 outputStack。第二个循环从 outputStack 里往外弹——因为它也是个栈，弹出顺序天然就是入栈的倒序，反转就这么完成了，不需要额外调用反转方法。

这个写法比直接模拟后序简单得多。直接模拟的话，需要区分「第一次经过这个节点」和「子树处理完回到这个节点」两种状态，得额外记录上一个访问的节点或者给每个节点打访问标记，代码要长不少。用双栈换来的代价是多占了 O(n) 的空间存中间结果，一般场景下这个交换是划算的。

const postorder = root => {
  if (!root) {
    return;
  }
  const outputStack = [];
  const stack = [root];

  while (stack.length) {
    const n = stack.pop();
    outputStack.push(n);
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);
  }

  while (outputStack.length) {
    const n = outputStack.pop();
    console.log(n.val);
  }
};

postorder(bt);