递归初相见——二叉树递归遍历的三种姿势|算法篇

遍历方式应从数据依赖反推。若父结点结果依赖左右子树，就要先得到孩子再处理父亲，对应后序；若利用二叉搜索树“左小、根中、右大”的约束输出有序值，则用中序。层序让距离根相同的结点连续出现，适合最短层数、逐层聚合和宽度问题。

四种遍历都至少访问每个结点一次，时间为 O(n)。深度优先保存当前根到叶的路径，辅助空间 O(h)；广度优先保存当前层的候选结点，最坏 O(w)。完全二叉树最后一层宽度接近 n/2，所以层序空间不能简单说成 O(log n)。

以一定的顺序规则，逐个访问二叉树的所有结点，这个过程就是二叉树的遍历。按照顺序规则的不同，遍历方式有以下四种：

• 先序遍历
• 中序遍历
• 后序遍历
• 层次遍历

按照实现方式的不同，遍历方式又可以分为以下两种：

• 递归遍历（先、中、后序遍历）
• 迭代遍历（层次遍历）

层次遍历的考察相对比较孤立，我们会把它放在后续的真题归纳解读环节来讲。这里我们重点要看的是先、中、后序遍历三兄弟——由于同时纠结了二叉树和“递归”两个大热命题点，又不属于“偏难怪”之流，遍历三兄弟一直是前端算法面试官们的心头好，考察热度经久不衰。

以求高度为例，函数契约是“返回以 node 为根的子树高度，空树高度为 -1”。当前层无需知道子树内部细节，只取左右返回值的较大者加一：

function height(root) {
  if (root === null) return -1
  return 1 + Math.max(height(root.left), height(root.right))
}

每个结点计算一次，时间 O(n)；调用栈空间 O(h)。不能因为局部变量少就说空间 O(1)，未返回的栈帧会随深度增长。用户可构造的超深树应改用显式栈并限制最大结点数和深度。

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。

简单来说，当我们看到一个函数反复调用它自己的时候，递归就发生了。“递归”就意味着“反复”，像咱们之前对二叉树的定义，就可以理解为是一个递归式的定义：

• 它可以没有根结点，作为一棵空树存在
• 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。

这个定义有着这样的内涵：如果我们想要创建一个二叉树结点作为根结点，那么它左侧的子结点和右侧的子结点也都必须符合二叉树结点的定义，这意味着我们要反复地执行“创建一个由数据域、左右子树组成的结点”这个动作，直到数据被分配完为止。

结合这个定义来看，每一棵二叉树都应该由这三部分组成：

对树的遍历，就可以看做是对这三个部分的遍历。这里就引出一个问题：三个部分中，到底先遍历哪个、后遍历哪个呢？我们此处其实可以穷举一下，假如在保证“左子树一定先于右子树遍历”这个前提，那么遍历的可能顺序也不过三种：

• 根结点 -> 左子树 -> 右子树
• 左子树 -> 根结点 -> 右子树
• 左子树 -> 右子树 -> 根结点

上述三个遍历顺序，就分别对应了二叉树的先序遍历、中序遍历和后序遍历规则。

在这三种顺序中，根结点的遍历分别被安排在了首要位置、中间位置和最后位置。

所谓的“先序”、“中序”和“后序”，“先”、“中”、“后”其实就是指根结点的遍历时机。

function traverse(root, order = 'pre') {
  if (!['pre', 'in', 'post'].includes(order)) throw new TypeError('unknown order')
  const result = []
  const visit = (node) => {
    if (node === null) return
    if (order === 'pre') result.push(node.val)
    visit(node.left)
    if (order === 'in') result.push(node.val)
    visit(node.right)
    if (order === 'post') result.push(node.val)
  }
  visit(root)
  return result
}

每个结点只在选定时机写入一次，时间 O(n)，递归栈 O(h)，结果数组 O(n)。若调用方只找第一个匹配项，应返回命中结果逐层短路或用生成器，避免继续遍历和收集完整数组。