递归与二叉树

二叉树的层序遍历

它和前面三种不一样

前中后序都是深度优先：一头扎到底，再回头。它们天然适合递归。

层序遍历是广度优先：先把第一层看完，再看第二层。 它没法用递归自然地写出来，得靠一个队列。

⭐ 值得单独讲，是因为它是后面 BFS 与最短路径那一章的原型。 图上的 BFS 跟这里的代码几乎一模一样，只多了一个 visited。

基本框架

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

  const q = [root];

  while (q.length > 0) {
    const sz = q.length;        // 🚨 关键：先把当前层的节点数存下来
    const level = [];

    for (let i = 0; i < sz; i++) {
      const node = q.shift();
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }

    res.push(level);
  }

  return res;
}

🚨 const sz = q.length 这一行是全篇最重要的

怎么知道「这一层结束了」？ 队列里同时躺着这一层剩下的节点和下一层刚加进来的节点， 光看队列本身分不出来。

答案是：进入 for 循环之前，队列里装的恰好就是完整的一层。 所以先把长度存进 sz，然后只弹 sz 次 —— 弹完就是这一层结束。

⚠️ 写成 for (let i = 0; i < q.length; i++) 会怎样：循环体里一边 shift 一边 push， q.length 每轮都在变，而 i 在跟它赛跑。拿一棵 7 节点的满二叉树试：

正确： [[1], [2,3], [4,5,6,7]]
错法： [[1,2,3,4], [5,6], [7]]

分组是乱的，但节点一个不少、拉平之后顺序还完全正确（都是 1,2,3,4,5,6,7）。

2000 棵随机树实测：

拉平后与正确答案相同    2000 / 2000  = 100%
连分组都碰巧相同         283 / 2000  = 14.1%

🚨 第一行是它难查的原因：错的只有「分层」这一个维度。 如果题目只要求按层序输出所有节点、不要求分层，这段代码永远能通过。

⚠️ 第二行更麻烦：有 14% 的树连分组都碰巧正确 —— 随手挑几棵小树当测试用例，很可能一棵都没暴露出问题。

分组具体怎么错还跟树的形状有关，换棵树又是另一种错法：

满二叉树 n=3    正确 [[1],[2,3]]
                错法 [[1,2],[3]]
满二叉树 n=7    正确 [[1],[2,3],[4,5,6,7]]
                错法 [[1,2,3,4],[5,6],[7]]
满二叉树 n=15   正确 [[1],[2,3],[4,5,6,7],[8,…,15]]
                错法 [[1,…,8],[9,10,11,12],[13,14],[15]]

⭐ 看出规律了：错法的第一组吞掉了一半节点，之后每组减半 —— 因为 i 和 q.length 在赛跑，而每弹一个就可能压入两个。

⚠️ shift() 的复杂度陷阱

JavaScript 的数组不是队列。q.shift() 要把后面所有元素往前挪一位，是 O(n)， 整体退化到 O(n²)。这不是纸上谈兵，实测（平衡树，两版都跑同一棵）：

n shift() 版 下标版 倍数
10,000 1.1 ms 0.4 ms 2.7×
50,000 58.1 ms 1.6 ms 36.9×
200,000 1,148.6 ms 5.1 ms 224.9×
800,000 81,613 ms 21.4 ms 3822×

🚨 n=80 万时是 81 秒 vs 21 毫秒。倍数随 n 线性增长，正是 O(n²) 的指纹 —— V8 对 shift() 有小数组优化，但规模上去之后完全兜不住。

📌 「算法题的数据量下通常无所谓」这句话要看题：n ≤ 10⁴ 时只差 2.7×，确实无所谓； 到 10⁵ 就已经差两个数量级，而这个规模在力扣上并不罕见。

正确写法是用下标当队头，不真的删元素：

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

  const q = [root];
  let head = 0;                 // 队头下标，代替 shift()

  while (head < q.length) {
    const sz = q.length - head;
    const level = [];

    for (let i = 0; i < sz; i++) {
      const node = q[head++];
      level.push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }

    res.push(level);
  }

  return res;
}

📌 代价是数组不会缩小（占用 O(n) 内存），但时间从 O(n²) 降到 O(n)。 数据量大时这是唯一能用的写法。

三个常见变体，都只改一行

右视图 —— 站在树的右边能看到的节点，也就是每层的最后一个：

if (i === sz - 1) res.push(node.val);

每层最大值 —— 把 level 换成一个数字：

levelMax = Math.max(levelMax, node.val);

之字形遍历 —— 奇数层反过来。在收集完这一层之后反转，不要改遍历方向：

res.push(depth % 2 === 0 ? level : level.reverse());

🚨 之字形有个诱人的错法：交替地「先压左」「先压右」。 它对第二层是对的，从第三层开始就乱了。实测：

n=7    正确      [[1], [3,2], [4,5,6,7]]
       交替压栈  [[1], [3,2], [6,7,4,5]]
                              ↑ 第 3 层开始不一致

n=15   正确      [[1], [3,2], [4,5,6,7], [15,14,13,12,11,10,9,8]]
       交替压栈  [[1], [3,2], [6,7,4,5], [13,12,15,14,9,8,11,10]]

⭐ 注意第 3 层错的方式：[6,7,4,5] 不是 [4,5,6,7] 的反转， 而是两两一组内部保序、组间顺序被换了 —— 因为上一层的入队顺序影响会往下传递， 每一层的错法都是前面所有层累积的结果，不是每层独立的。

👉 所以改遍历方向解决不了问题：遍历照常、输出时反转才对。

往后看

把这段代码搬到图上，只需要加一个 visited 集合防止重复访问和死循环 —— 那就是 BFS。

⭐ 而 BFS 有一个二叉树层序遍历不需要、但在图上极其重要的性质： 它第一次到达某个节点时，走过的层数就是最短距离。 因为它是一层一层扩散的，不可能跳过更近的层先到远的。 「最少几步能到」这一类题几乎全靠这一条。

这些放在 BFS 算法框架那一篇讲。回到深度优先这边， 两种思维里的遍历视角， 往下走就是回溯与 DFS。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。