LeetCode 二叉树的层序遍历 广度优先遍历题解

题目

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

解题思路

• 层序遍历顺序就是广度优先遍历
• 不过在遍历的时候需要记录当前节点所处的层级，方便将其添加到不同的数组中
• 关键技巧是每一轮循环开始前先把队列当前的长度存下来，这个长度就是当前层的节点数，只处理这么多个，剩下的属于下一层

这道题的返回值是 number[][] 而不是 number[]，这是它和普通 BFS 唯一的差别，也是全部难点所在。普通 BFS 只要一个队列不停出队入队就行，不用管节点属于第几层；这里必须知道层的边界。

一个自然的想法是在队列里存 [节点, 层号] 这样的二元组，靠层号分组。能做对，但要多维护一份数据。更省的做法是利用队列本身的状态：某一时刻队列里如果恰好只有第 k 层的所有节点，那此刻的 queue.length 就是第 k 层的节点数。把这个数记下来，循环这么多次，出队的全是第 k 层的，同时它们的孩子（第 k+1 层）被推到队尾。一轮结束后队列里又恰好只剩第 k+1 层的全部节点，状态自洽，可以继续下一轮。

题解

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  // 空树直接返回空数组，这是必须处理的边界
  if (!root) return [];

  const res = [];
  const queue = [root];

  while (queue.length) {
    // 快照当前层的节点数，后面 queue 会被 push 进下一层的节点，
    // 所以这个值必须在循环前存下来，不能在 for 条件里写 queue.length
    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);
    }

    res.push(currentLevel);
  }

  return res;
};

const levelSize = queue.length 这一行是整道题的核心。如果偷懒写成 for (let i = 0; i < queue.length; i++)，queue.length 每次比较都重新求值，而循环体里在往队尾 push 新节点，条件永远满足不了边界，结果就是把整棵树的节点全塞进第一层的数组里。这是这道题最高频的错法。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

时间上每个节点恰好入队一次、出队一次，所以是 O(n)。

空间上主要是队列占的，峰值等于最宽那一层的节点数。满二叉树的最后一层约有 n/2 个节点，所以最坏是 O(n)。返回值 res 本身存了全部 n 个值，通常不算进额外空间。

用双数组代替 shift 优化常数

上面的写法有个性能瑕疵：Array.prototype.shift() 是 O(n) 的，它要把后面所有元素整体前移一位。总体复杂度虽然在 LeetCode 的数据量下（本题节点数 ≤ 2000）看不出差别，但严格说会退化到 O(n²)。

两种改法。一是用头指针，不真的删元素：

var levelOrder = function (root) {
  if (!root) return [];
  const res = [];
  const queue = [root];
  let head = 0; // 只移动指针

  while (head < queue.length) {
    const levelSize = queue.length - head;
    const currentLevel = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(currentLevel);
  }
  return res;
};

二是用两个数组滚动，当前层和下一层分开放，连 levelSize 都不用记了，代码反而更清晰：

var levelOrder = function (root) {
  if (!root) return [];
  const res = [];
  let currentLevel = [root];

  while (currentLevel.length) {
    // 当前层的值直接 map 出来，就是结果的一行
    res.push(currentLevel.map(node => node.val));

    const nextLevel = [];
    for (const node of currentLevel) {
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }
    currentLevel = nextLevel;
  }
  return res;
};

这个版本没有任何 shift，层的边界由数组的替换天然划出。我个人更喜欢这一版，因为它把「层」这个概念显式表达成了一个变量，读代码的人不需要在脑子里模拟队列状态。

DFS 也能做

层序遍历给人的第一反应是 BFS，但 DFS 同样可以，只要在递归时把层号（也就是递归深度）带下去，用它当结果数组的下标：

var levelOrder = function (root) {
  const res = [];

  function dfs(node, depth) {
    if (!node) return;
    // 第一次到达这一层，先给它开一个数组
    if (res.length === depth) res.push([]);
    res[depth].push(node.val);
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }

  dfs(root, 0);
  return res;
};

if (res.length === depth) res.push([]) 这行是关键：因为先序遍历总是从左往右、从浅往深地首次抵达每一层，所以当递归到深度 depth 而 res 里还没有这一层时，说明这是第一次到达，此时 res.length 恰好等于 depth。

同样是 O(n) 时间，空间是 O(h)（递归栈深度），树平衡时比 BFS 的 O(n) 更省。代价是树退化成链表时递归会爆栈，而 BFS 不会。

边界用例

提交前过一遍这几个，能挡掉大部分错误：

• 空树 root = null → 应返回 []，不是 [[]]。这是最容易忽略的一个，忘了 if (!root) return [] 就会返回一个含空数组的数组。
• 单节点 root = [1] → [[1]]。
• 只有左子树的链 [1, 2, null, 3] → [[1], [2], [3]]，每层一个节点，验证层的划分没串。
• 左右不对称 [3, 9, 20, null, null, 15, 7] → [[3], [9, 20], [15, 7]]。这是题目给的示例，验证 null 孩子被正确跳过、没有把 null 塞进队列。

最后一条特别提一下：if (node.left) queue.push(node.left) 里的判断不能省。如果无条件 push，null 会进队列，下一轮 node.val 就报 Cannot read properties of null。有些人习惯改成先入队再在出队时判空，两种写法都对，但不能一半一半。

这道题的变体

102 是一系列题的模板，掌握后这几道基本是改两行：

• 107. 二叉树的层序遍历 II — 自底向上返回。把最后 res.reverse()，或者每层用 res.unshift(currentLevel) 插到头部。前者更好，unshift 是 O(n)。
• 199. 二叉树的右视图 — 每层只取最后一个，把 res.push(currentLevel) 换成 res.push(currentLevel[currentLevel.length - 1])。
• 637. 二叉树的层平均值 — 每层求平均，改成 res.push(sum / levelSize)。
• 103. 二叉树的锯齿形层序遍历 — 奇偶层交替方向，加一个层号计数，偶数层正常 push、奇数层 currentLevel.reverse() 再 push。
• 111. 二叉树的最小深度 — BFS 遇到第一个叶子节点就返回当前层号，这比 DFS 求最小深度更快，因为不用把整棵树走完。

能看出这些题共用同一个「分层」骨架，是这道题真正要学到的东西。