算法篇 ｜ 二叉树

前言

二叉树是算法面试中的”万题之源”。很多看似复杂的问题，拆解到最后都回归到二叉树的遍历和递归。如果你能熟练地在二叉树上做 DFS 和 BFS，很多其他数据结构和算法的题目也会变得容易。

对前端工程师来说，二叉树并不陌生——DOM 树就是树结构，虚拟 DOM 的 diff 算法、组件树的渲染、路由匹配，底层都涉及树的遍历。所以掌握二叉树不仅是为了面试，也是理解这些前端核心机制的基础。

二叉树的题目看起来种类繁多，但核心就两件事：怎么遍历和在遍历的过程中做什么。本章我们会系统地讲解四种遍历方式（前/中/后/层序）的递归和迭代实现，然后通过经典题目帮你建立”拿到一道二叉树题，第一步该怎么想”的思维框架。

诊断自测

Q1：前序遍历、中序遍历、后序遍历的区别是什么？分别在什么场景下使用？

Q2：BFS 和 DFS 在二叉树上的区别是什么？各自的典型应用场景是什么？

Q3：如何验证一棵二叉搜索树（BST）是否合法？

一、二叉树的遍历

1.1 节点定义

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

1.2 前序遍历（Pre-order）：根 → 左 → 右

递归版：

function preorderTraversal(root) {
  const result = [];

  function dfs(node) {
    if (node === null) return;
    result.push(node.val);  // 先处理当前节点
    dfs(node.left);
    dfs(node.right);
  }

  dfs(root);
  return result;
}

迭代版（用栈模拟递归）：

function preorderTraversal(root) {
  if (root === null) return [];

  const result = [];
  const stack = [root];

  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.val);

    // 先压右再压左，这样左子节点先出栈
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return result;
}

1.3 中序遍历（In-order）：左 → 根 → 右

递归版：

function inorderTraversal(root) {
  const result = [];

  function dfs(node) {
    if (node === null) return;
    dfs(node.left);
    result.push(node.val);  // 在中间处理当前节点
    dfs(node.right);
  }

  dfs(root);
  return result;
}

迭代版：

function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let curr = root;

  while (curr !== null || stack.length > 0) {
    // 一路向左，把所有左子节点压栈
    while (curr !== null) {
      stack.push(curr);
      curr = curr.left;
    }

    // 弹出栈顶（最左的未处理节点）
    curr = stack.pop();
    result.push(curr.val);

    // 转向右子树
    curr = curr.right;
  }

  return result;
}

中序遍历的特殊意义：对 BST 做中序遍历，得到的是一个有序序列。这个性质在很多 BST 相关的题目中都会用到。

1.4 后序遍历（Post-order）：左 → 右 → 根

递归版：

function postorderTraversal(root) {
  const result = [];

  function dfs(node) {
    if (node === null) return;
    dfs(node.left);
    dfs(node.right);
    result.push(node.val);  // 最后处理当前节点
  }

  dfs(root);
  return result;
}

迭代版（技巧：前序的变体，最后反转）：

function postorderTraversal(root) {
  if (root === null) return [];

  const result = [];
  const stack = [root];

  while (stack.length > 0) {
    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(); // 最后反转
}

后序遍历的典型应用：当你需要先知道子树的结果才能计算当前节点时，就用后序。比如：计算树的高度、判断是否平衡、删除节点等。

1.5 层序遍历（Level-order）：逐层从左到右

层序遍历使用 BFS，核心数据结构是队列。

function levelOrder(root) {
  if (root === null) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}

关键细节：levelSize = queue.length 必须在 for 循环之前取值，因为循环中会往队列里加新元素。levelSize 记录的是当前层的节点数。

二、BFS vs DFS

怎么选？ 一般来说：

• 题目涉及”层”或”最短”→ BFS
• 题目涉及”路径”、“子树”、“递归定义” → DFS
• 如果都可以，DFS 通常代码更简洁（递归写法）

三、经典题目

3.1 二叉树的最大深度（LeetCode 104）

给定一棵二叉树，找出其最大深度。

这是入门级的二叉树题目，但它完美展示了递归的思维方式。

function maxDepth(root) {
  if (root === null) return 0;

  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);

  return Math.max(leftDepth, rightDepth) + 1;
}

一行代码的含义：当前树的最大深度 = 左子树深度和右子树深度的较大值 + 1。

也可以用 BFS 做——层数就是深度：

function maxDepth(root) {
  if (root === null) return 0;

  const queue = [root];
  let depth = 0;

  while (queue.length > 0) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    depth++;
  }

  return depth;
}

复杂度：时间 O(n)，空间 O(h)（递归）或 O(w)（BFS）。

3.2 翻转二叉树（LeetCode 226）

翻转一棵二叉树（所有节点的左右子树互换）。

function invertTree(root) {
  if (root === null) return null;

  // 交换左右子树
  [root.left, root.right] = [root.right, root.left];

  // 递归翻转子树
  invertTree(root.left);
  invertTree(root.right);

  return root;
}

这道题有个有趣的典故：Homebrew 的作者 Max Howell 在 Google 面试时因为没做出这道题而被拒了。他在推特上吐槽说”我造了大多数 Mac 开发者都用的工具，但我不会在白板上翻转二叉树”。

复杂度：时间 O(n)，空间 O(h)。

3.3 验证二叉搜索树（LeetCode 98）

给定一棵二叉树，判断它是否是合法的二叉搜索树（BST）。

BST 的定义：左子树所有节点 < 根 < 右子树所有节点。注意是”所有节点”，不仅仅是直接子节点。

方法一：递归验证（传递值域）

function isValidBST(root) {
  return validate(root, -Infinity, Infinity);
}

function validate(node, min, max) {
  if (node === null) return true;

  if (node.val <= min || node.val >= max) {
    return false;
  }

  return (
    validate(node.left, min, node.val) &&
    validate(node.right, node.val, max)
  );
}

方法二：中序遍历检查单调性

function isValidBST(root) {
  let prev = -Infinity;

  function inorder(node) {
    if (node === null) return true;

    if (!inorder(node.left)) return false;

    if (node.val <= prev) return false;
    prev = node.val;

    return inorder(node.right);
  }

  return inorder(root);
}

复杂度：时间 O(n)，空间 O(h)。

3.4 二叉树的最近公共祖先（LeetCode 236）

给定一棵二叉树和两个节点 p、q，找出它们的最近公共祖先（LCA）。

这是面试高频题，也是理解后序遍历的好例子。

function lowestCommonAncestor(root, p, q) {
  // base case
  if (root === null || root === p || root === q) {
    return root;
  }

  // 后序遍历：先递归左右子树
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // 当前层逻辑
  if (left !== null && right !== null) {
    return root; // p 和 q 分别在左右子树中，当前节点就是 LCA
  }

  return left !== null ? left : right;
}

理解这段代码的关键：

1. 如果当前节点是 p 或 q，直接返回当前节点
2. 递归查找左右子树
3. 如果左右子树的返回值都不为 null，说明 p 和 q 分别在左右子树中，当前节点就是 LCA
4. 如果只有一边不为 null，说明 p 和 q 都在那一边，返回那边的结果

复杂度：时间 O(n)，空间 O(h)。

四、二叉树题的解题思维框架

拿到一道二叉树题，按这个思路想：

1. 能否用递归定义？ 大多数二叉树题可以分解为”当前节点 + 左子树 + 右子树”的递归结构
2. 用什么遍历顺序？
   • 需要先处理当前节点 → 前序
   • 需要在 BST 上有序处理 → 中序
   • 需要先知道子树结果 → 后序
   • 需要逐层处理 → 层序（BFS）
3. 递归函数返回什么？ 高度、布尔值、节点、还是其他信息
4. 需要什么辅助信息？ 有时需要传递额外参数（如值域范围、路径和等）

常见误区

误区一：“递归就是 DFS，迭代就是 BFS”

不对。DFS 可以用递归实现，也可以用栈迭代实现。BFS 用队列迭代实现。“递归 vs 迭代”和”DFS vs BFS”是两个独立的维度。

误区二：“前序/中序/后序只是遍历顺序不同，实际效果一样”

不一样。它们决定了”处理当前节点”的时机，这对结果有本质影响。比如验证 BST 必须用中序（利用有序性），计算深度用后序更自然（先知道子树深度）。选错遍历顺序可能导致代码复杂度大增甚至写不出来。

误区三：“层序遍历直接用 queue.shift() 就行了”

Array.shift() 的时间复杂度是 O(n)（因为要移动所有元素），严格来说用数组模拟队列的性能并不好。面试中一般可以接受，但如果面试官追问，你应该知道可以用双指针（维护一个 front 指针）或链表来实现 O(1) 的出队操作。

误区四：“二叉搜索树的验证只需要检查每个节点和它的直接子节点的关系”

这是一个经典的 Bug。仅检查 node.left.val < node.val < node.right.val 是不够的。比如下面这棵树通过了局部检查但不是合法 BST：

    5
   / \
  1   6
     / \
    3   7

节点 3 虽然 < 6（它的父节点），但它 < 5（它祖父节点），不应该出现在 5 的右子树中。所以必须传递值域范围来验证。

小结

二叉树是算法面试的核心题型，掌握了二叉树的遍历和递归思维，很多其他问题都能迎刃而解。

核心要点

1. 四种遍历：前序（根左右）、中序（左根右）、后序（左右根）、层序（BFS）
2. 递归三要素：base case、递归调用、当前层逻辑
3. 选择遍历顺序：根据”处理当前节点”的时机来选择
4. BFS vs DFS：层相关问题用 BFS，路径/子树问题用 DFS
5. BST 的特殊性质：中序遍历有序，验证需要传递值域范围

本章思维导图

练习挑战

第一题 ⭐：二叉树的最小深度（LeetCode 111）

给定一棵二叉树，找出其最小深度（根节点到最近叶子节点的路径上的节点数量）。

function minDepth(root) {
  if (root === null) return 0;

  // 如果只有右子树，不能返回 0（左子树为空不算叶子）
  if (root.left === null) return minDepth(root.right) + 1;
  if (root.right === null) return minDepth(root.left) + 1;

  return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

function minDepth(root) {
  if (root === null) return 0;
  const queue = [root];
  let depth = 1;

  while (queue.length > 0) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (node.left === null && node.right === null) return depth;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    depth++;
  }

  return depth;
}

第二题 ⭐⭐：二叉树的右视图（LeetCode 199）

给定一棵二叉树，返回从右侧看到的节点值（每层最右边的节点）。

function rightSideView(root) {
  if (root === null) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (i === size - 1) {
        result.push(node.val); // 每层最后一个节点
      }
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }

  return result;
}

第三题 ⭐⭐⭐：二叉树的序列化与反序列化（LeetCode 297）

设计一个算法将二叉树序列化为字符串，以及从字符串反序列化回二叉树。

function serialize(root) {
  const result = [];

  function dfs(node) {
    if (node === null) {
      result.push('null');
      return;
    }
    result.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }

  dfs(root);
  return result.join(',');
}

function deserialize(data) {
  const nodes = data.split(',');
  let index = 0;

  function dfs() {
    if (index >= nodes.length || nodes[index] === 'null') {
      index++;
      return null;
    }

    const node = new TreeNode(Number(nodes[index]));
    index++;
    node.left = dfs();
    node.right = dfs();

    return node;
  }

  return dfs();
}

自我检测

• 能默写前序、中序、后序遍历的递归实现
• 能用栈实现至少一种遍历的迭代版本
• 能写出层序遍历（BFS），并正确处理”按层收集”的逻辑
• 能说清楚 DFS 和 BFS 的区别、各自的数据结构和适用场景
• 能用递归求二叉树的最大深度，并解释递归的含义
• 能验证 BST，并解释为什么仅检查局部关系是不够的
• 能求两个节点的最近公共祖先，并解释后序遍历在其中的作用
• 拿到一道二叉树题时，能快速判断用什么遍历顺序和递归返回值