102. 二叉树的层序遍历

题目描述

给定二叉树根节点 root，按从上到下、从左到右的顺序返回每一层的节点值。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

题型判断

题目要求把节点“按层”分组返回，这是 BFS 的典型信号。

层序遍历的关键不是单纯遍历所有节点，而是要知道每一层的边界在哪里。因此在处理某一层之前，需要先记录当前队列中属于这一层的节点数量 levelSize。

核心思路

空树直接返回空数组。
根节点入队。
进入每一层时，固定当前层节点数 levelSize。
保存节点值，并将左右孩子加入队尾。
本层处理完后，把结果加入答案。

队列 [3]            → 取出 3，下一层入队 [9,20]
队列 [9,20]         → 取出 9、20，下一层入队 [15,7]
队列 [15,7]         → 取出 15、7

这里的队列示意表示“当前待处理的节点”。代码实现中使用 head 指针模拟出队，所以数组里已经访问过的节点不会立刻删除。

代码实现

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

  const result = [];
  const queue = [root];
  let head = 0;

  while (head < queue.length) {
    const levelSize = queue.length - head;
    const level = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head++];
      level.push(node.val);

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

    result.push(level);
  }

  return result;
};

head 表示当前队头位置，每处理一个节点就向后移动一位。这样可以避免使用 shift()，因为 JavaScript 数组从头部删除元素可能触发整体搬移。

复杂度分析

时间复杂度：O(n)，每个节点入队、出队各一次。
空间复杂度：O(n)。

当前实现用 head 指针模拟出队，queue 中访问过的节点不会被删除，最坏情况下会保存所有节点。如果使用真正的队列结构，只看遍历过程中的待处理节点，辅助空间可以理解为 O(w)，其中 w 是二叉树的最大宽度。计入返回结果时一定是 O(n)。

边界与易错点

空树返回 []，不是 [[]]。
levelSize 要在进入内层循环前固定。
不建议使用 shift() 出队；JavaScript 数组头删可能产生 O(n) 的元素移动。
使用 head 指针时，循环条件应该是 head < queue.length，不能只判断 queue.length > 0。
只有一个根节点时，返回 [[root.val]]。
链状二叉树也可以正常处理，只是每一层只有一个节点。

ON THIS PAGE

#102. 二叉树的层序遍历

#题目描述

#题型判断

#核心思路

#代码实现

#复杂度分析