二叉树的层序遍历

题目描述

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

示例

示例 1：

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

    3
   / \
  9  20
     / \
    15  7

输出: [[3], [9, 20], [15, 7]]

示例 2：

输入: root = [1]
输出: [[1]]

示例 3：

输入: root = []
输出: []

示例 4：

输入: root = [1, 2, 3, 4, null, null, 5]

      1
     / \
    2   3
   /     \
  4       5

输出: [[1], [2, 3], [4, 5]]

解题思路

使用 BFS（广度优先搜索）+ 队列实现。核心技巧是用 levelSize 记录当前层的节点数量，通过内层循环一次处理完当前层的所有节点，并将下一层节点入队。

步骤：

1. 将根节点入队。
2. 当队列不为空时，记录当前队列长度 levelSize。
3. 循环 levelSize 次，每次出队一个节点，收集其值，并将其左右子节点入队。
4. 将当前层的结果加入最终结果数组。
5. 重复步骤 2-4 直到队列为空。

代码实现

/**
 * 二叉树的层序遍历
 * @param {TreeNode} root - 二叉树根节点
 * @returns {number[][]} 按层组织的节点值数组
 */
function levelOrder(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];
    while (queue.length > 0) {
        const levelSize = queue.length;
        const level = [];
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            level.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(level);
    }
    return result;
}

复杂度分析

• 时间复杂度：O(n)，每个节点入队、出队各一次。
• 空间复杂度：O(n)，队列中最多存储一层的节点数，最坏情况下（完全二叉树的最后一层）为 n/2。

root = [3,9,20,null,null,15,7]

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