二叉树遍历深度解析

一句话概括

遍历就是”按什么顺序把树的每个节点访问一遍”。口诀好记——前序根左右、中序左根右、后序左右根、层序逐层从左到右——但面试真正考的是：为什么是这个顺序、它解决什么问题、递归怎么改成迭代。

DOM 树、虚拟 DOM、组件树、AST 抽象语法树……前端到处是树。掌握四种遍历，你才谈得上”会操作树”，而不是天天 querySelector 一把梭。

核心知识点

1. 前序遍历（根 → 左 → 右）

先访问根，再递归左右子树。最适合”复制 / 序列化树”——因为根最先出现，重建时最方便。

// 递归版：最直观，O(n) 时间 O(h) 空间（h 为树高）
function preorder(root, res = []) {
  if (!root) return res;
  res.push(root.val);
  preorder(root.left, res);
  preorder(root.right, res);
  return res;
}

// 迭代版：用栈模拟，先压右再压左，保证弹出时"左先于右"
function preorderIter(root) {
  if (!root) return [];
  const res = [], stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res;
}

// 应用：前序 + `#` 标记法序列化（LeetCode 297）
function serialize(root) {
  const out = [];
  (function dfs(n) {
    if (!n) { out.push('#'); return; }
    out.push(n.val); dfs(n.left); dfs(n.right);
  })(root);
  return out.join(',');
}

2. 中序遍历（左 → 根 → 右）

对二叉搜索树（BST），中序结果天然升序——这是验证 BST、找第 K 小元素的理论基础。

// 迭代版中序：先一路向左把节点压栈，左空了才访问、再转向右
function inorderIter(root) {
  const res = [], stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    res.push(cur.val);
    cur = cur.right;
  }
  return res;
}

// 应用：验证 BST —— 中序必须严格递增
function isValidBST(root) {
  let prev = -Infinity;
  const stack = [], cur = root;
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    if (cur.val <= prev) return false;
    prev = cur.val;
    cur = cur.right;
  }
  return true;
}

3. 后序遍历（左 → 右 → 根）

访问根之前，左右子树都已处理完，因此适合”自底向上”的计算（树高、直径、释放资源）。

// 递归版：子结果先出，再算父节点
function maxDepth(root) {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

// 迭代版技巧：前序"根→右→左"反转即得"左→右→根"
function postorderIter(root) {
  if (!root) return [];
  const res = [], stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return res.reverse();
}

4. 层序遍历（BFS，逐层从左到右）

用队列实现，天然按层组织，是求”最短路径 / 按层处理”的首选。

// 用 head 指针代替 shift，把出队从 O(n) 降到 O(1)
function levelOrder(root) {
  if (!root) return [];
  const res = [], queue = [root];
  let head = 0;
  while (head < queue.length) {
    const len = queue.length - head;
    const level = [];
    for (let i = 0; i < len; i++) {
      const node = queue[head++];
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res; // [[1], [2,3], [4,5,6]]
}

四种遍历时间都是 O(n)；DFS（递归）空间 O(h)，BFS 空间 O(w)（w 为最大层宽）。

其实你每天都在用

• React Fiber 渲染：构建 Fiber 树是前序（父→子→兄弟），工作循环用”可中断的深度优先”做时间切片
• Vue 模板编译：AST 生成后靠遍历做静态标记、收集依赖
• DOM 遍历：TreeWalker / NodeIterator 本质是前序
• 二叉搜索树：中序遍历直接得到有序数组，不用额外排序
• JSON.stringify 一棵树：递归（前序）把节点序列化
• 在组件树里找最近节点：BFS 层序能保证”离根最近”的先被找到

常见误解（FAQ）

❌ 误区一：”递归写法够用了，迭代没必要学”

递归在树很高（链表状、上万层）时会 “Maximum call stack size exceeded” 栈溢出；而且递归一旦开始不能中途暂停。React 之所以用迭代的 Fiber 而非递归，就是为了”可中断渲染”。面试几乎必问”递归怎么转迭代”。

❌ 误区二：”前序 + 后序能唯一确定一棵树”

不能。只有”中序 + 前序”或”中序 + 后序”才能唯一确定。因为某节点只有左子树或只有右子树时，前序和后序区分不出”左”还是”右”。

❌ 误区三：”层序遍历必须用队列，不能用递归”

能用递归，但那本质还是 DFS（带层级参数的深度优先），不是真正的 BFS——要找”第 3 层某节点”时它会遍历全部节点，且队列版内存只和最宽层有关。理解”层序 = BFS = 队列”才是正解。

❌ 误区四：”中序遍历对普通二叉树有什么用？”

中序的核心价值在 BST（升序）。对普通二叉树它只是”左根右”顺序，没特殊含义。面试题里凡出现”有序”“第 K 小”，第一时间该想到 BST 中序。

一句话总结

四种遍历不是四段要背的代码，而是四种”看待树的顺序”——前序复制、中序取序、后序自底向上算、层序按层铺开；先想清楚”我要按什么顺序碰节点”，代码自然就出来了。