二叉树的前序、中序、后序遍历怎样用递归和迭代写？

简答

前序、中序、后序都是深度优先遍历，区别只在什么时候记录当前节点：前序是先记自己再走左右子树，中序是走完左子树再记自己，后序是左右子树都走完才记自己。名字里的“前中后”说的就是根节点的位置。

递归写法三种几乎一样，只是把“记录当前节点”这一行放在两次递归调用的前面、中间或后面。迭代写法要自己用数组当栈，代替函数调用栈：前序弹出就访问，先压右子节点再压左子节点，这样左边先出栈；中序先一路把左子节点压进栈，压到底再弹出访问，然后转到它的右子树；后序最省事的写法是按“根右左”访问，最后把结果反转成“左右根”。

中序遍历在二叉搜索树上会得到从小到大的序列，常用来验证二叉搜索树、找第 k 小的数；后序适合先算完子树再算自己的场景，比如统计目录大小。迭代写法的用处是树很深时不会撑爆调用栈。

要注意，三种写法时间都是 O(n)，栈的大小取决于树高。后序“反转”的写法得到的顺序是对的，但访问节点的真实时机不是后序，如果要在访问时做依赖子树结果的事，需要用记录上一个访问节点的写法。

递归和迭代六种写法

先看三个递归函数里 result.push 的位置，再对比三个迭代函数怎样用栈。

JavaScript

function fromLevelOrder(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = { val: values[0], left: null, right: null };
  const queue = [root];
  let i = 1;
  for (let head = 0; i < values.length; head++) {
    const node = queue[head];
    for (const side of ['left', 'right']) {
      if (i < values.length && values[i] !== null) {
        node[side] = { val: values[i], left: null, right: null };
        queue.push(node[side]);
      }
      i++;
    }
  }
  return root;
}

function recursive(order) {
  return function traverse(root, result = []) {
    if (!root) return result;
    if (order === 'pre') result.push(root.val);
    traverse(root.left, result);
    if (order === 'in') result.push(root.val);
    traverse(root.right, result);
    if (order === 'post') result.push(root.val);
    return result;
  };
}

function preorder(root) {
  const result = [];
  const stack = root ? [root] : [];
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}

function inorder(root) {
  const result = [];
  const stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    result.push(node.val);
    node = node.right;
  }
  return result;
}

function postorder(root) {
  const result = [];
  const stack = root ? [root] : [];
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return result.reverse();
}

const tree = fromLevelOrder([1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]);
console.log(preorder(tree).join(',')); // 1,2,4,5,6,7,3,8,9
console.log(inorder(tree).join(',')); // 4,2,6,5,7,1,3,9,8
console.log(postorder(tree).join(',')); // 4,6,7,5,2,9,8,3,1

const same = ['pre', 'in', 'post'].map((order, i) =>
  recursive(order)(tree).join(',') === [preorder, inorder, postorder][i](tree).join(','),
);
console.log(same.join(',')); // true,true,true
console.log(inorder(fromLevelOrder([1, null, 2, 3])).join(',')); // 1,3,2
console.log(preorder(null).length); // 0

示例的树和输出取自 LeetCode 三道题的第二个示例。recursive 把三种递归合在一个函数里，只是为了让人看清它们只差 push 的位置。

前序为什么先压右子节点？栈是后进先出的，后压进去的左子节点会先弹出，所以访问顺序是根、左、右。

中序的外层循环条件为什么是 node || stack.length？node 不为空表示还有一棵子树没开始走，栈不为空表示还有节点在等着访问。内层循环把左边一路压进栈，弹出的节点左子树一定已经处理完了，这时访问它，再把 node 指向它的右子树，右子树为空的话，下一轮就直接弹出上一层的节点。

后序为什么能靠反转？把前序的压栈顺序改成先左后右，访问顺序就是“根右左”，整个反转过来正好是“左右根”。代价是结果要全部收集完才能反转，不能边遍历边输出。

不反转的后序怎么写

如果访问时要立刻用到子树的结果，需要真正按后序访问。做法是在中序的基础上多记一个 prev：弹出前先看栈顶，如果它有右子树、而且右子树还没访问过（top.right !== prev），就转去走右子树；否则才弹出访问它，并把 prev 设成它。多叉树用显式栈做前序遍历的写法见《怎样用显式栈实现树的前序遍历？》。

常见追问

有没有不用栈也不用递归的遍历？

有，叫 Morris 遍历。它利用叶子节点空着的右指针，临时指回中序的后继节点，走完后再把指针改回来，额外空间是 O(1)。缺点是遍历过程中会临时修改树。

怎样用中序遍历验证二叉搜索树？

二叉搜索树的中序结果一定严格递增。遍历时记住上一个访问的值，遇到当前值不大于上一个值就返回 false，不需要把结果全部存下来。

层序遍历属于这三种吗？

不属于。前中后序都是深度优先，用栈；层序是广度优先，用队列，见《二叉树怎样层序遍历、求最大深度？》。