102. 二叉树的层序遍历

Origin: LeetCode 102

题目描述

给定二叉树的根节点 root，返回其节点值的层序遍历结果（即逐层从左到右访问）。返回一个二维数组，每个子数组是同一层的所有节点值。

示例

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

      3
     / \
    9  20
       / \
      15  7

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

Input: root = [] Output: []

约束

• 树中节点数目范围是 [0, 2000]
• -1000 <= Node.val <= 1000

关键信息

• 逐层从左到右，返回二维数组
• BFS + 队列
• 关键：每次处理一整层，记录当前层节点数

Resolution

我的解法

function levelOrder(root: TreeNode | null): number[][] {
    if (!root) return []
 
    let queue: TreeNode[] = [root]
    const result = []
    while (queue.length) {
        const tmpRes: number[] = []
        const tmpQueue: TreeNode[] = []
        queue.forEach((node) => {
            tmpRes.push(node.val)
            if (node?.left) {
                tmpQueue.push(node.left)
            }
            if (node?.right) {
                tmpQueue.push(node.right)
            }
        })
        queue = [...tmpQueue]
        result.push(tmpRes)
    }
    return result
}

标准解法（单队列 + levelSize）

function levelOrder(root: TreeNode | null): number[][] {
    if (!root) return []
    const queue: TreeNode[] = [root]
    const result = []
    while (queue.length) {
        const levelSize = queue.length
        const tmpRes: number[] = []
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!
            tmpRes.push(node.val)
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
        result.push(tmpRes)
    }
    return result
}

单队列，先记录当前层节点数（levelSize），处理完就进入下一层。不需要 tmpQueue。

解题思路

BFS + 队列。每轮处理一整层：

1. 遍历当前 queue 里所有节点，收集值到 tmpRes
2. 子节点收集到 tmpQueue
3. queue 替换为 tmpQueue（进入下一层）
4. 每层的 tmpRes push 到 result

复杂度

• 时间：O(n)，每个节点访问一次
• 空间：O(n)，队列最多存一层的节点