算法学习台/算法实验台/56 天打卡/141 题/LC102
题型地图56天全屏141题

当前：LC102 · 二叉树的层序遍历 · 首次出现于 Day 17 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC101LC104 →
41 / 141回到 Day 17 卡片141 题索引
LC102Medium二叉树BFS队列

二叉树的层序遍历

队列负责让节点从上到下出场；每轮开始时冻结的 levelSize，负责把同一层牢牢分在一起。

题目是什么

按从上到下、从左到右的顺序，把二叉树每一层分别输出。

解决什么问题

既保证 BFS 顺序，又保留层与层之间的边界。

核心结论

每轮先冻结队列长度，只处理这批节点；新加入的孩子留给下一轮。

01交互算法精讲

先说结论：这道题到底解决什么

普通 BFS 只能给出访问顺序，怎样让队列明确知道一层在哪里结束，并保证下一层新入队的节点不会混进当前层？

中心结论：每轮先冻结队列长度，只处理这批节点；新加入的孩子留给下一轮。

读完必须能回答
  1. 1.为什么每轮开始时的 queue 恰好装着当前层全部节点？
  2. 2.为什么必须先冻结 levelSize，而不能让内层循环一直处理到队列为空？
  3. 3.左右孩子的入队顺序如何决定同一层的输出顺序？
02交互算法精讲

完整题目与题意拆解

给定二叉树根节点 root，返回节点值的层序遍历结果，也就是逐层从左到右访问所有节点。

返回值是二维数组。外层代表层，内层保存这一层的节点值。

  • • 空树返回 []，不是 [[]]。
  • • 同一层保持从左到右。
  • • 下一层节点由当前层节点的孩子产生。
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

普通 BFS 能得到 [3,9,20,15,7]，但题目还要求知道哪些节点属于同一层。

队列中始终按发现顺序保存待处理节点。每轮开始时，队列中已有的节点恰好组成当前层。

关键变量不是 queue 本身，而是 levelSize := len(queue)。它把轮开始时已有的节点圈起来，之后新入队的孩子不会混进本层。
动画 1 · 题意扫描

输出为什么需要明确的层边界

先展示整棵树和期望的二维结果，再让不同层以横向色带分开，明确算法必须回答的不只是访问顺序。

Step 1/20%
目标：按层分组
3
第 1 层
9
第 2 层
20
第 2 层
15
第 3 层
7
第 3 层
[[3], [9,20], [15,7]]
看完带走：题目要求按层分组，不是得到一条普通 BFS 序列。
03交互算法精讲

第一层方案：暴力做法

可以先做一次普通 BFS 得到一维顺序，再为每个节点额外记录 depth，最后按 depth 分组。

这个方案仍需维护节点与深度的配对。更直接的做法是在每轮开始时利用队列现状识别整层。

queue 保存 (node, depth)
依次弹出后放入 result[depth]
额外状态：每个节点都携带 depth
优化不是把 O(n) 变成更小的数量级，而是让数据结构直接表达“当前层”，减少冗余状态。
动画 2 · 暴力重复

队列一直处理到空会发生什么

演示根节点出队后孩子立即加入，如果内层条件跟随 queue 长度变化，下一层就会被错误吞进当前层。

Step 1/30%
处理当前层节点
3
9
20
15
7
queue
空
当前层
[3]
看完带走：不冻结本轮数量，层与层就会混在一起。

优化方向：如果目标就是从上到下逐层输出，BFS 的队列顺序与题意完全一致，状态也更直观。

04交互算法精讲

整体地图：先做什么，再做什么

层序遍历的难点不是把节点放进队列，而是划清层与层的边界。我们先观察轮开始时的队列快照，再把这一刻的长度冻结成 levelSize。

本轮只消费 levelSize 个旧节点；处理过程中加入队尾的孩子属于下一层，必须留到下一轮。这样队列既负责从上到下，冻结长度又负责按层分组。

  • • 队列维护访问先后顺序。
  • • levelSize 固定本轮消费数量。
  • • level 切片只收集本轮节点值。
层序遍历 = BFS 队列 + 每轮开始时冻结的层边界。
05交互算法精讲

把队列在轮开始时拍成一张当前层快照

根节点先入队。每轮外层循环开始时，队列中保存的恰好是尚未处理的最浅一层节点。令 levelSize=len(queue)，就相当于给这批节点加上一条不可移动的层边界。

处理一个节点时，它的孩子会进入队尾。因为本轮只执行 levelSize 次，这些新节点不会被提前消费；本轮结束时，队列便自然变成下一层的完整快照。

处理根 3 时，冻结长度是 1。即使 9 和 20 随后入队，本轮也只弹出 3；下一轮才冻结长度 2。
关键动作不是读取队列长度，而是在孩子入队之前保存这个长度。
动画 3 · 核心概念

冻结快照给当前层画一道边界

轮开始时用括号锁住队列前 levelSize 个元素，后续新入队节点显示在边界之外等待。

Step 1/30%
初始化队列
3
9
20
15
7
queue
3
看完带走：levelSize 是当前层快照，不是一个持续变化的长度。
06交互算法精讲

固定消费旧节点，让新孩子在队尾等待下一轮

每轮创建容量为 levelSize 的 level。内层循环固定执行 levelSize 次：弹出队首、记录节点值，再按左后右把非空孩子加入队尾。

内层结束后把 level 追加到 result。此刻上一层已完全出队，下一层已按从左到右的顺序排在队列中，外层循环可以重复同一过程。

  • • 弹出使用 FIFO，不能替换成栈。
  • • 左孩子先入队，保证同层从左到右。
  • • 空树直接返回空结果，而不是包含一个空层。
  • • 队列可以增长，但本轮计数不能跟着增长。

空树直接返回空结果。根节点先入队；只要队列不空，就创建当前层数组并冻结队列长度。

循环固定次数，每次弹出队首，把值加入 level，再按左、右顺序把非空孩子加入队尾。最后把 level 加入答案。

内层不能写成“while queue 不空”。否则刚加入的孩子会立刻被继续消费，所有层会挤到同一个数组里。
动画 4 · 机制构建

消费旧节点，排好下一层

节点从队首逐个离开，左右孩子从队尾进入；当前层结果与下一层队列在画面中保持分区。

Step 1/40%
处理当前层节点
3
9
20
15
7
queue
空
当前层
[3]
看完带走：FIFO 负责顺序，固定次数负责分层。
07交互算法精讲

为什么每一轮都恰好输出一整层

用层数归纳。开始时队列只有根节点，因此第一轮快照正好是第 0 层。假设某轮开始时队列按从左到右保存第 k 层全部节点。

固定消费 levelSize 次会恰好移除第 k 层。每个节点按左后右加入其孩子，所以所有第 k+1 层节点按父节点从左到右、同父节点左到右的顺序进入队尾。

本轮不消费新孩子，因此下一轮开始时队列恰好是第 k+1 层。归纳成立，result 中每个切片都准确对应一层。

冻结长度保证层不混，FIFO 与左后右入队保证层内顺序不乱。
正确性抓手
  • • 轮开始时队列恰好包含当前层全部节点，顺序为从左到右。
  • • 固定消费 levelSize 次，确保本轮不会处理新加入的下一层孩子。
  • • 孩子按左后右入队，所以归纳得到下一轮仍保持从左到右。
08交互算法精讲

完整执行过程

重点观察队列上方的冻结括号：青色槽位属于本轮，后来进入的琥珀色槽位只能等待下一轮。

  1. 1把根节点 3 入队，第一轮冻结 levelSize=1。
  2. 2弹出 3 写入当前 level，并把 9、20 依次加入队尾。
  3. 3本轮已经消费 1 个旧节点，提交 [3]，不继续处理新入队节点。
  4. 4第二轮冻结 levelSize=2，依次处理 9 和 20，并让 15、7 留在队尾。
  5. 5重复直到队列为空，得到 [[3],[9,20],[15,7]]。
动画 5 · 完整执行

完整跑出三层二维结果

依次冻结 1、2、2 个节点，展示每轮提交的 level，并同步累积最终二维结果。

Step 1/50%
levelSize = 1
3
9
20
15
7
queue
3
当前层
[]
看完带走：每轮提交一次，队列便自然过渡到下一层。
09交互算法精讲

把动画和 Go 代码逐行对应

每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立， 再看对应代码，而不是先背模板。

动画 6 · 代码映射

代码中的两个循环分别控制什么

高亮外层的“还有层”、冻结的 levelSize 和固定次数内层循环，让每行代码对应一个队列动作。

Step 1/40%
levelSize = 1
3
9
20
15
7
queue
3
当前层
[]
看完带走：外层按层推进，内层只消费冻结快照中的节点。
Step 1
先看清二维输出

题目不仅要访问顺序，还要保留每一层的边界。

empty-check
Step 2
根节点先入队

BFS 必须先处理最早发现的节点。

enqueue-root
Step 3
冻结第一层人数 1

本轮只处理开始时已有的 1 个节点，新孩子属于下一层。

outer-loop · freeze-level-size · new-level
Step 4
3 出队，进入当前层

出队的节点属于冻结范围，因此属于当前层。

dequeue-node · append-node
Step 5
9 和 20 排到下一轮

左孩子先入队，保证下一层从左到右；冻结次数仍是 1，不会继续消费它们。

enqueue-left · enqueue-right
Step 6
第一层提交完成

固定次数已经执行完，本轮边界清晰结束。

append-level
Step 7
第二层冻结为 2

本轮冻结两次，所以两位同层节点会一起提交。

freeze-level-size · dequeue-node · append-node
Step 8
15 和 7 留在冻结边界外

levelSize 早已固定为 2，enqueue 不会改变本轮循环次数。

enqueue-left · enqueue-right · append-level
Step 9
队列清空，三层全部完成

每个节点都恰好入队一次、出队一次。

append-level · return-result
Step 10
不冻结会把三层混在一起

队列不空并不代表当前层还没结束，它可能只装着下一层。

freeze-level-size · fixed-count-loop
10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法
1func levelOrder(root *TreeNode) [][]int {2    if root == nil { return [][]int{} }3 4    result := make([][]int, 0)5    queue := []*TreeNode{root}6 7    for len(queue) > 0 {8        levelSize := len(queue)9        level := make([]int, 0, levelSize)10        for i := 0; i < levelSize; i++ {11            node := queue[0]; queue = queue[1:]12            level = append(level, node.Val)13            if node.Left != nil { queue = append(queue, node.Left) }14            if node.Right != nil { queue = append(queue, node.Right) }15        }16        result = append(result, level)17    }18    return result19}
最小测试集合
// 主例：三层且最后一层来自同一父节点
fmt.Println(levelOrder(buildTree([]any{3, 9, 20, nil, nil, 15, 7}))) // [[3] [9 20] [15 7]]
// 空树不能返回一个空层
fmt.Println(levelOrder(nil)) // []
// 单节点
fmt.Println(levelOrder(&TreeNode{Val: 1})) // [[1]]
// 链状树仍需逐层分组
fmt.Println(levelOrder(buildTree([]any{1, 2, nil, 3}))) // [[1] [2] [3]]
11交互算法精讲

正确性与复杂度

时间复杂度 O(n)

每个节点只入队一次、出队一次，并被写入结果一次。

空间复杂度 O(w)

队列最多同时保存树的最大层宽 w 个节点；若计入返回结果则总输出空间为 O(n)。

12交互算法精讲

最容易写错的地方

错误 1

内层一直循环到 queue 为空，导致下一层混进当前层。

错误 2

用栈替代队列，遍历退化成 DFS。

错误 3

右孩子先入队，破坏同层从左到右顺序。

错误 4

空树返回 [[]] 而不是 []。

13交互算法精讲

最后复盘：带走逻辑链

  1. 1.queue 决定从上到下。
  2. 2.levelSize 决定当前层边界。
  3. 3.左、右孩子的入队顺序决定同层顺序。
  4. 4.同一模型可迁移到 LC107、LC199 和多源 BFS。
面试表达
  1. 1.用队列做 BFS，根节点先入队。
  2. 2.每轮开始保存 levelSize=len(queue)，它就是当前层节点数。
  3. 3.固定弹出 levelSize 个节点，记录值并把左右孩子加入队尾。
  4. 4.每轮结束追加 level；时间 O(n)，额外队列空间 O(w)。