Binary Tree Level Order Traversal（二叉树的层序遍历）

题目 / Problem

中文： 给定一棵二叉树的根节点 root，返回其节点值的层序遍历结果，即从上到下逐层访问，每层从左到右排列。

English: Given the root of a binary tree, return the level-order traversal of its nodes' values—that is, from left to right, level by level.

示例 / Examples

Example 1

二叉树层序遍历示例 / Binary tree level-order traversal example

Input:  root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

        3          → [3]
       / \
      9  20        → [9, 20]
         / \
        15  7      → [15, 7]

按照从上到下、每层从左到右的顺序，结果为 [[3],[9,20],[15,7]]。
Reading from top to bottom and left to right within each level produces [[3],[9,20],[15,7]].

Example 2

Input:  root = [1]
Output: [[1]]

单节点树只有一层。
A single-node tree has only one level.

Example 3

Input:  root = []
Output: []

空树不包含任何层，因此返回空数组。
An empty tree contains no levels, so return an empty array.

约束 / Constraints

树中的节点数在 [0, 2000] 范围内。
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

解题思路：广度优先搜索 / Approach: Breadth-First Search

层序遍历天然适合使用队列。队列先进先出的特性可以保证：
Level-order traversal naturally uses a queue. Its first-in, first-out behavior guarantees that:

上一层节点先于下一层节点被处理。
Nodes in an earlier level are processed before nodes in a later level.
同一层中，左侧节点先于右侧节点被处理。
Within a level, left-side nodes are processed before right-side nodes.

处理步骤：
Processing steps:

如果 root === null，直接返回 []。
If root === null, return [] immediately.
将根节点加入队列。
Enqueue the root node.
每轮开始时记录当前队列中的本层节点数 levelSize。
At the start of each round, record the number of current-level nodes as levelSize.
连续取出 levelSize 个节点，将它们的值保存到当前层数组。
Dequeue exactly levelSize nodes and store their values in the current-level array.
按先左后右的顺序，将非空子节点加入队列。
Enqueue non-null children in left-to-right order.
当前层处理完后，将它加入最终结果。
Append the completed level to the final result.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = val ?? 0;
 *   this.left = left ?? null;
 *   this.right = right ?? null;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
function levelOrder(root) {
  if (root === null) {
    return [];
  }

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

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

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

      if (node.left !== null) {
        queue.push(node.left);
      }

      if (node.right !== null) {
        queue.push(node.right);
      }
    }

    result.push(level);
  }

  return result;
}

这里使用索引 front 读取队列，而没有使用 JavaScript 数组的 shift()。shift() 可能在每次调用时移动剩余元素，带来额外开销。
An index named front reads from the queue instead of using JavaScript's shift(), which may move all remaining elements on every call.

执行过程 / Walkthrough

以 Example 1 为例：
For Example 1:

第 1 层 / Level 1

处理前队列 / Queue before: [3]
本层节点数 / levelSize: 1
本层结果 / level: [3]
加入子节点 / Enqueue: 9, 20
处理后队列 / Remaining queue: [9, 20]

第 2 层 / Level 2

处理前队列 / Queue before: [9, 20]
本层节点数 / levelSize: 2
本层结果 / level: [9, 20]
加入子节点 / Enqueue: 15, 7
处理后队列 / Remaining queue: [15, 7]

第 3 层 / Level 3

处理前队列 / Queue before: [15, 7]
本层节点数 / levelSize: 2
本层结果 / level: [15, 7]
加入子节点 / Enqueue: none
处理后队列 / Remaining queue: []

最终结果：
Final result:

[[3],[9,20],[15,7]]

为什么要提前保存 `levelSize`？ / Why Capture `levelSize` First?

处理当前层节点时，它们的子节点会不断加入队列。如果循环直接使用持续变化的 queue.length，下一层节点可能会被错误地放入当前层。
While current-level nodes are processed, their children are continually added to the queue. If the loop uses the changing queue.length directly, next-level nodes may be incorrectly included in the current level.

在每轮开始时固定：
At the start of each round, fix:

const levelSize = queue.length - front;

然后只处理这 levelSize 个节点，就能准确划分层级。
Processing exactly these levelSize nodes keeps level boundaries correct.

复杂度 / Complexity

设树中有 n 个节点，最大宽度为 w。
Let the tree contain n nodes and have maximum width w.

时间复杂度：O(n)，每个节点入队和读取各一次。
Time: O(n), because every node is enqueued and read once.
空间复杂度：O(n)，队列数组在整个过程中保存所有节点引用；若使用可回收已出队空间的标准队列，活动队列最多为 O(w)。
Space: O(n) for this array-backed queue, which retains all node references. With a standard queue that reclaims dequeued storage, the active queue is at most O(w).
返回结果本身需要 O(n) 空间。
The returned result itself requires O(n) space.

DFS 解法：按深度分组 / DFS Approach: Group by Depth

也可以使用深度优先搜索，并将节点值放入与其深度对应的数组：
Depth-first search can also place each node value into the array corresponding to its depth:

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

  function traverse(node, depth) {
    if (node === null) {
      return;
    }

    if (result.length === depth) {
      result.push([]);
    }

    result[depth].push(node.val);
    traverse(node.left, depth + 1);
    traverse(node.right, depth + 1);
  }

  traverse(root, 0);
  return result;
}

先递归左子树再递归右子树，可以保证每一层内部仍按从左到右的顺序加入。
Recursing into the left subtree before the right preserves left-to-right order within each level.

时间复杂度 / Time: O(n)
空间复杂度 / Space: O(h) 递归调用栈，加上 O(n) 返回结果；h 是树高。
The recursion stack uses O(h) space, in addition to the O(n) result; h is the tree height.

BFS 与 DFS 对比 / BFS vs. DFS

方法 / Method	时间 / Time	辅助空间 / Auxiliary Space	特点 / Notes
BFS	`O(n)`	活动队列通常记为 `O(w)`	与层序遍历定义直接对应 / Directly matches level order
DFS	`O(n)`	`O(h)`	使用深度作为结果下标 / Uses depth as the result index

BFS 更直观地体现“逐层处理”，通常是本题的首选解法。
BFS directly models level-by-level processing and is generally the preferred solution.

易错点 / Common Pitfalls

空树应返回 []，不能返回 [[]]。
Return [] for an empty tree, not [[]].
每轮必须先固定 levelSize，再处理当前层。
Capture levelSize before processing each level.
子节点应按先左后右的顺序加入队列。
Enqueue the left child before the right child.
返回结果是二维数组，每一层对应一个独立数组。
The result is a two-dimensional array with one separate array per level.
不要把所有节点值放入同一个一维数组。
Do not place every node value into a single flat array.
DFS 写法需要以深度作为结果数组的下标，并先创建不存在的层。
In the DFS version, use depth as the result index and create each level before adding values.

Binary Tree Level Order Traversal