102. 二叉树的层序遍历

题目描述

给你二叉树的根节点 root，返回其节点值的 层序遍历。

也就是说，要逐层地，从左到右访问所有节点。

示例 1

text

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

示例 2

text

输入：root = [1]
输出：[1](<1.md>)

示例 3

text

输入：root = []
输出：[]

约束

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

核心思路

这题的关键词是：

逐层
从左到右

只要看到“按层遍历”，第一反应就应该是：

BFS（广度优先搜索）

因为 BFS 本来就是一层一层向外扩展的，非常适合二叉树层序遍历。

当然，这题也可以用 DFS 来做，只不过 DFS 不是按“搜索顺序”天然分层，而是需要额外记录当前节点所在的层数。

所以这题至少有两种常见做法：

解法一：BFS + 队列（推荐）
解法二：DFS + 深度参数

先理解：什么叫层序遍历？

比如这棵树：

text

按层来看：

第 0 层：3
第 1 层：9, 20
第 2 层：15, 7

所以层序遍历结果就是：

text

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

注意它不是：

前序遍历
中序遍历
后序遍历

而是按“层”来分组的遍历。

解法一：BFS + 队列

这是这题最标准、最推荐掌握的做法。

思路拆解

BFS 会把同一层的节点放在一起处理。

做法是：

先把根节点放进队列
每次处理当前队列里的所有节点
这些节点正好就是同一层
处理时把它们的左右孩子加入队列
进入下一轮时，队列里就变成了下一层节点

这样我们就能一层一层地收集答案。

一步一步写出算法

第一步：处理空树情况

如果根节点为空，直接返回空数组。

if (root === null) {
    return []
}

第二步：准备答案数组和队列

const result: number[][] = []
const queue: TreeNode[] = [root]

第三步：开始按层遍历

只要队列不空，就还有节点没处理。

while (queue.length > 0) {
    ...
}

第四步：先记录当前层节点个数

const levelSize = queue.length

为什么要先记下来？

因为：

当前队列里这些节点，正好是同一层
这一轮只处理这 levelSize 个节点
它们的孩子会被放进队列，留到下一层处理

第五步：遍历当前层

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

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

第六步：把这一层加入答案

result.push(level)

代码实现（TypeScript）

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function levelOrder(root: TreeNode | null): number[][] {
    if (root === null) {
        return []
    }

    const result: number[][] = []
    const queue: TreeNode[] = [root]

    while (queue.length > 0) {
        const levelSize = queue.length
        const level: number[] = []

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!
            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
}

复杂度分析

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

因为每个节点都会入队、出队各一次。

这一解法的优缺点

优点：

最符合题意
最容易理解“按层遍历”
是标准解法

缺点：

如果直接用 shift()，在 JS / TS 里常数稍大

解法二：DFS + 深度参数

这个做法更适合理解：

虽然 DFS 不是按层遍历
但只要记录当前节点深度
也能把节点放进对应层的数组里

思路拆解

我们递归遍历整棵树，并额外传一个参数：

text

depth

表示当前节点在第几层。

当访问到一个节点时：

如果 result[depth] 这一层还不存在，就先创建一个空数组
把当前节点值放进去
继续递归左右子树，深度都加 1

这样最后也能得到按层分组的结果。

一步一步写出算法

第一步：定义结果数组

const result: number[][] = []

第二步：定义 DFS 函数

const dfs = (node: TreeNode | null, depth: number): void => {
    ...
}

第三步：处理空节点

if (node === null) {
    return
}

第四步：确保当前层数组存在

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

这说明当前是第一次访问到这一层。

第五步：把当前节点值放进去

result[depth].push(node.val)

第六步：递归左右子树

dfs(node.left, depth + 1)
dfs(node.right, depth + 1)

代码实现（TypeScript）

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0
        this.left = left ?? null
        this.right = right ?? null
    }
}

function levelOrder(root: TreeNode | null): number[][] {
    const result: number[][] = []

    const dfs = (node: TreeNode | null, depth: number): void => {
        if (node === null) {
            return
        }

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

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

    dfs(root, 0)
    return result
}

复杂度分析

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

主要来自：

递归调用栈
结果数组本身

这一解法的优缺点

优点：

能帮助你理解 DFS 和层信息如何结合
代码也很简洁

缺点：

不如 BFS 那么贴合题意
如果树很深，会依赖递归栈

两种解法对比

解法	时间复杂度	空间复杂度	特点
BFS + 队列	`O(n)`	`O(n)`	最标准，最推荐
DFS + 深度参数	`O(n)`	`O(n)`	更适合理解递归分层

如果你是第一次做层序遍历，建议优先掌握 BFS。

手动模拟一遍 BFS

以这棵树为例：

text

初始状态

队列：

text

[3]

结果：

text

[]

第 1 层

当前层节点数：

text

处理后：

收集到 [3]
把 9 和 20 入队

此时：

text

result = [3](<3.md>)
queue = [9, 20]

第 2 层

当前层节点数：

text

处理后：

收集到 [9, 20]
9 没有孩子
20 的孩子 15、7 入队

此时：

text

result = [[3], [9,20]]
queue = [15, 7]

第 3 层

当前层节点数：

text

处理后：

收集到 [15, 7]
它们都没有孩子

最终：

text

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

面试时最容易错的点

1. “层序遍历”优先想到 BFS

因为 BFS 本来就是按层扩展。

这是最自然的匹配。

2. BFS 里要先记录当前层大小

const levelSize = queue.length

这个值非常关键。

因为当前层处理过程中，队列里会不断加入下一层节点。

如果不先固定当前层大小，就会把下一层也一起处理进去。

3. DFS 也能做，但要带 `depth`

如果你直接 DFS 但不记录层数，就没法知道当前节点该放进哪一层数组。

4. 空树返回空数组

[]

不是 [[]]。

一句话总结

这题的本质是：

把二叉树节点按层分组，从上到下、从左到右输出。

想写标准解：用 BFS + 队列
想练递归：用 DFS + 深度参数

102. 二叉树的层序遍历

题目描述

示例 1

示例 2

示例 3

约束

核心思路

先理解：什么叫层序遍历？

解法一：BFS + 队列

思路拆解

一步一步写出算法

第一步：处理空树情况

第二步：准备答案数组和队列

第三步：开始按层遍历

第四步：先记录当前层节点个数

第五步：遍历当前层

第六步：把这一层加入答案

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：DFS + 深度参数

思路拆解

一步一步写出算法

第一步：定义结果数组

第二步：定义 DFS 函数

第三步：处理空节点

第四步：确保当前层数组存在

第五步：把当前节点值放进去

第六步：递归左右子树

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

两种解法对比

手动模拟一遍 BFS

初始状态

第 1 层

第 2 层

第 3 层

面试时最容易错的点

1. “层序遍历”优先想到 BFS

2. BFS 里要先记录当前层大小

3. DFS 也能做，但要带 depth

4. 空树返回空数组

一句话总结

推荐你最后记住的标准写法

3. DFS 也能做，但要带 `depth`