LeetCode 102. 二叉树的层序遍历
目录
题目描述
考察公司：美团
题意分析
题目给定一棵二叉树，要求返回一个二维列表：第
i个内层列表恰好是深度为i的所有节点值，且同一层内按从左到右排列。真正的难点藏在返回值的形态里。如果只要求输出一串扁平序列，那么只需要保证访问顺序满足「浅的节点先访问、同深度左边先访问」就够了；可题目要求按层分组，这就多出一份负担——除了访问顺序，还必须知道每一层在哪里结束。也就是说，光「按正确顺序遍历完所有节点」不够，遍历过程中还要能回答「当前这一层还剩几个节点」或者「当前节点属于第几层」，否则拿到的只是一条连续的节点流，没法切分成一层一层。
题意本身透露了几个信号。分组只由节点的深度决定，与节点值、与树是否平衡、是否完全都无关；同一层内的相对顺序完全由左右孩子的位置决定，所以任何处理方式都必须保证左孩子先于右孩子被收集；另外，层与层之间没有任何重叠，每个节点只属于唯一一层，这说明每个节点只需要被处理一次，不需要回头修补。
边界情形有三类。第一类是空树，此时应返回长度为 0 的二维列表，而不是「含一个空层」的
[[]]，这两者在判题时是不同的答案。第二类是只有单侧孩子的斜树，每层只有一个节点，层数等于节点数，层数可以远大于任何一层的宽度。第三类是节点值本身不可信赖——不能假定它们非负或互不相同，因此不能挑一个「特殊值」塞进容器当分层哨兵，那个值完全可能真实出现在树里。
解法：BFS 队列按层遍历
核心思路
队列保证节点按层、从左到右访问。每轮开始先记录当前队列长度，只处理这一批节点；本轮入队的孩子自然留到下一层。
解题步骤
- 空树直接返回空结果，非空时将根节点入队。
- 每轮先记录
levelSize = queue.size()，它就是当前层的节点数。- 出队
levelSize个节点，收集节点值，并按先左后右的顺序将非空孩子入队。- 将当前层加入结果，直到队列为空。
代码实现
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>(levelSize);
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}
return result;
}
}
func levelOrder(root *TreeNode) [][]int {
result := make([][]int, 0)
if root == nil {
return result
}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
level := make([]int, 0, levelSize)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点入队、出队各一次。
- 空间复杂度：$O(w)$，
w为二叉树的最大宽度；不计返回结果。
关键点总结
- 外层循环每次处理一整层，队列负责维持从左到右的顺序。
- 必须在处理当前层前固定
levelSize，避免把下一层提前消费。- 孩子按先左后右入队，空节点不入队。
易错点总结
- 在循环条件里动态读取队列长度，会因孩子不断入队而破坏分层。
- 空树未提前返回，可能把空节点入队并触发空指针。
- 复用同一个层列表，会让多层结果引用同一份数据。
- Go 中
make([]int, levelSize)已创建了指定长度，再append会产生多余零值；这里只预分配容量。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 103. 二叉树的锯齿形层序遍历 | 中等 | 分层骨架不变，多一步「按层号决定本层是否反向」 |
| 107. 二叉树的层序遍历 II | 中等 | 层内容完全相同，只是要求自底向上，收尾整体反转或每层插到头部 |
| 116. 填充每个节点的下一个右侧节点指针 | 中等 | 不收集层内容而是把同层节点串成 next 链，完美二叉树可做到常数空间 |
| 117. 填充每个节点的下一个右侧节点指针 II | 中等 | 同样连 next，但树形任意，需要跳过缺失的孩子去找下一个候选 |
| 199. 二叉树的右视图 | 中等 | 每层只保留最后一个节点，本层列表退化成「取末位元素」 |
| 429. N 叉树的层序遍历 | 中等 | 孩子从固定的左右两个变成 children 列表，入队处改为遍历子节点数组 |
| 513. 找树左下角的值 | 中等 | 只要最底层最左值，可改成先右后左入队后取最后一个出队节点，无需存层 |
| 515. 在每个树行中找最大值 | 中等 | 本层列表换成一个滚动的最大值变量，输出降为一维 |
| 637. 二叉树的层平均值 | 简单 | 需要层内累加和与层节点数，levelSize 从边界标记变成参与计算的除数 |
| 662. 二叉树最大宽度 | 中等 | 关心层宽而非层内容，要给节点配下标以把中间的空位也算进宽度 |
| 958. 二叉树的完全性检验 | 中等 | 反其道而行：孩子不判空照样入队，看第一个空位之后是否还有真实节点 |
| 1302. 层数最深叶子节点的和 | 中等 | 只要最深一层的和，可以每层覆盖上一层的结果，不必保留全部层 |
| LCR 044. 在每个树行中找最大值 | 中等 | 515 的换皮题，与本题的差别只在「每层输出一个最大值而非整层」 |
| LCR 045. 找树左下角的值 | 中等 | 513 的换皮题，只取最后一层的第一个节点 |
| LCR 046. 二叉树的右视图 | 中等 | 199 的换皮题，只取每层最后一个节点 |
| 剑指 Offer 32 - I. 从上到下打印二叉树 | 中等 | 输出是扁平一维数组，不需要分组，正好用来对照「快照层长度」的必要性 |
| 剑指 Offer 32 - II. 从上到下打印二叉树 II | 简单 | 与本题等价的题面，可以直接套同一份代码 |
| 剑指 Offer 32 - III. 从上到下打印二叉树 III | 中等 | 等价于 103 的锯齿输出，奇偶层方向交替 |
| 面试题 04.03. 特定深度节点链表 | 中等 | 每层结果从列表换成单链表，分层骨架不变、只改本层的收集容器 |