二叉树（6 题）

LeetCode 预定义结构（JS 版）：

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

二叉树通用套路：递归三问（终止条件 / 单层逻辑 / 返回值） + 遍历顺序（前中后序 = 什么时候处理根）。 返回目录：4.algorithms/题单.md

1. 二叉树的中序遍历（迭代）

题意：返回中序遍历结果。 思路：一路向左压栈，弹出来访问，再转向右子树。递归写法谁都会，面试常要求迭代。 复杂度：时间 O(n)，空间 O(h)，h 是树高。 易错：循环条件是 cur || stack.length，两个条件缺一不可（栈非空说明还有右子树没走）。 追问：「前序 / 后序怎么改？」——前序入栈时就收集；后序用「根右左」遍历再整体反转。

function inorderTraversal(root) {
  const res = [];
  const 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;
}

2. 二叉树的层序遍历

题意：按层返回节点值。 思路：BFS。每轮先记下当前队列长度，那就是这一层的节点数。 复杂度：时间 O(n)，空间 O(n)。 易错：必须在进入内层循环前固定 size，否则会把下一层的节点混进来。 易错：别用 queue.shift() 出队——数组头部删除是 O(n)，整棵树会退化到 O(n²)。用 head 指针（或双端队列）出队，才是真正的 O(n)。

function levelOrder(root) {
  if (!root) return [];
  const res = [];
  const queue = [root];
  let head = 0; // 出队用 head 指针，避免 shift() 的 O(n) 搬移
  while (head < queue.length) {
    const size = queue.length; // 固定当前层节点数
    const level = [];
    for (let i = head; i < size; i++) {
      const node = queue[i];
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    head = size; // 本层出完，head 指向下一层开头
    res.push(level);
  }
  return res;
}

3. 二叉树的最大深度

题意：求最大深度（根到最远叶子节点的节点数）。 思路：递归，深度 = 1 + max(左深度, 右深度)。 复杂度：时间 O(n)，空间 O(h)（递归栈）。 追问：「能用 BFS 做吗？」——可以，层数就是深度，而且不怕深树爆栈。

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

4. 翻转二叉树

题意：左右子树互换。 思路：递归交换左右孩子，再分别翻转。 复杂度：时间 O(n)，空间 O(h)。 追问：「能不能用迭代？」——可以，BFS 或栈遍历，每个节点交换左右孩子。

function invertTree(root) {
  if (!root) return null;
  const tmp = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(tmp);
  return root;
}

5. 二叉树的最近公共祖先

题意：找两个节点的最近公共祖先（LCA）。 思路：后序遍历。左右子树各找到一个，当前节点就是答案。 复杂度：时间 O(n)，空间 O(h)。 易错：题目保证两个节点都存在，所以找到一个就能直接返回。 追问：「是二叉搜索树呢？」——利用有序性：都在左就去左，都在右就去右，否则当前节点就是答案。

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root; // 两边各有一个，当前节点就是 LCA
  return left || right;
}

6. 路径总和 III

题意：统计路径和等于 targetSum 的路径条数，路径不必从根开始，但必须向下。 思路：前缀和 + 回溯。cnt[x] 表示从根到当前节点的路径上，前缀和为 x 的节点个数。 复杂度：时间 O(n)，空间 O(n)。 易错：回溯时要把当前前缀和减掉；cnt[0] = 1 是初始值，代表「路径从根开始」这一条。 易错：JS 的 Map 取值要写 (cnt.get(k) || 0)，直接相加会得到 NaN。

function pathSum(root, targetSum) {
  const cnt = new Map([[0, 1]]); // 前缀和 -> 出现次数
  let res = 0;

  const dfs = (node, cur) => {
    if (!node) return;
    cur += node.val;
    res += cnt.get(cur - targetSum) || 0; // 有几条路径以当前节点结尾
    cnt.set(cur, (cnt.get(cur) || 0) + 1);
    dfs(node.left, cur);
    dfs(node.right, cur);
    cnt.set(cur, cnt.get(cur) - 1); // 回溯
  };

  dfs(root, 0);
  return res;
}