LeetCode 剑指 Offer 32 - II. 从上到下打印二叉树 II
目录
题目描述
题意分析
给一棵二叉树，要求把节点值按「同一层放进同一个子列表、层与层之间从上到下、层内从左到右」的形式输出。
和普通遍历最大的区别在于输出结构带层次：结果不是一维序列而是二维列表，所以遍历时不仅要按正确顺序访问节点，还必须知道每个节点属于第几层，或者至少知道一层的边界在哪里。
「从左到右」这个要求限定了同层节点的入队顺序必须是先左后右，一旦顺序反了，即使分层正确，层内序列也是错的。
边界有两个：空树要返回空列表而不是含一个空列表的结果；单节点树应返回只有一层、一个元素的二维列表。
解法：队列分层遍历
核心思路
先想最直接的做法：递归地做前序遍历，同时把当前深度作为参数传下去，按深度把值塞进对应的子列表。这个做法是对的，也确实常见，但它的结果依赖「先左后右」的递归顺序来保证层内有序，而且要额外处理「深度第一次出现时新建子列表」，逻辑上不如自顶向下的扫描直观。
换个视角：这题本质是逐层地把树「剥」下来。如果手里有第 k 层的全部节点，那么把它们从左到右依次展开孩子，得到的正好就是第 k+1 层的全部节点，且顺序天然正确。这就是一个先进先出的过程——队列是这个过程的精确对应物。
剩下的唯一问题是分层。队列里同时可能混着两层的节点，光靠「队列非空」无法判断层的边界。关键观察是：在开始处理第 k 层之前，队列里的元素恰好就是第 k 层的全部节点，一个不多一个不少。因此只要在进入内层循环之前先把
size = queue.size()记下来，接着只弹 size 次，弹出的就一定是完整的一层。由此得到的不变量是：每次外层循环开始时，队列中按从左到右的顺序恰好存放着某一层的全部节点。初始只放根节点时它是第 0 层，成立；一轮内层循环弹光这 size 个节点、并按序追加它们的非空孩子，结束后队列里就是下一层的全部节点，顺序仍是从左到右，不变量得以保持。
注意 size 必须在内层循环之前一次性取好。如果把
queue.size()直接写进循环条件，队列会在循环体内被孩子撑大，边界随之漂移，分层立刻失效。
解题步骤
- 先判空树并返回空列表。这不只是防空指针，更是为了避免结果里多出一个空的层列表。
- 把根节点入队，作为第 0 层的初始状态，让不变量在第一轮就成立。
- 外层循环条件是队列非空，因为「还有节点没处理」等价于「还有下一层」。
- 每轮先把当前队列长度存进 size，并新建一个本层的列表。先取长度是分层的全部技巧所在，取完之后队列怎么变都不影响这一轮要弹的个数。
- 内层循环弹出 size 个节点，把值追加进本层列表；对每个节点依次检查左孩子、右孩子，非空则入队。先左后右保证下一层的顺序仍是从左到右。
- 内层循环结束后把本层列表加入答案。此时队列里恰好是下一层的全部节点，不变量成立，可以进入下一轮。
以树
[3,9,20,null,null,15,7]走一遍，即根为 3，左孩子 9 是叶子，右孩子 20 的左右孩子分别是 15 和 7。队列初始为
[3]。第一轮 size = 1，弹出 3，本层列表为[3]；3 的左孩子 9 入队、右孩子 20 入队，队列变成[9, 20]；答案为[[3]]。第二轮 size = 2，注意这里必须是 2 而不是循环中途变化的长度。弹出 9，本层列表
[9]，9 无孩子；弹出 20，本层列表[9, 20]，20 的左孩子 15、右孩子 7 依次入队，队列变成[15, 7]；答案为[[3], [9,20]]。第三轮 size = 2，弹出 15 和 7，本层列表
[15, 7]，两者都是叶子不入队，队列变空；答案为[[3], [9,20], [15,7]]。外层循环条件不再满足，返回结果。若把 size 换成实时的队列长度，第二轮弹出 20 时队列被撑到 3，循环会继续弹出 15，第二层就会错误地变成
[9, 20, 15]——这正是分层写法的关键差别所在。
代码实现
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; 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);
}
}
res.add(level);
}
return res;
}
}
func levelOrder(root *TreeNode) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) > 0 {
size := len(queue)
level := make([]int, 0, size)
for i := 0; i < size; i++ {
node := queue[i]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
queue = queue[size:]
res = append(res, level)
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点恰好入队一次、出队一次，出队时只做常数次操作（记录值、检查两个孩子）。
- 空间复杂度：$O(n)$，队列在最坏情况下要装下最宽的一层；完全二叉树的最后一层约有 n/2 个节点，因此队列规模是线性的。返回值本身不计入额外空间。
关键点总结
- 广度优先遍历要分层时，唯一的技巧就是在处理每层前先固定
size = queue.size()，把「队列非空」和「本层未处理完」这两个条件彻底分开。- 队列之所以能保证层内从左到右，靠的是入队顺序先左后右，顺序即结果，这类题不需要任何排序。
- 想清楚不变量「每轮外层循环开始时队列里恰好是一整层」，就能把这道题的变体全部推导出来：取每层最后一个即右视图，取每层最大值即 515，把层列表反转或用头插即 107。
- 空树的返回值要和题目约定对齐，返回空列表而不是含空列表的结果，这类小差异在判题里是硬错误。
- 面试视角：面试官常追问「不用队列能不能做」，答案是可以，DFS 携带深度参数同样能分层，但它天然适合的是「按深度归组」，而要求严格按层推进（比如层内还需要处理下一层指针的 116/117）时队列写法更自然；再追问空间时要点明瓶颈是最宽一层而非树高。
易错点总结
- 错误写法：内层循环条件直接写
while (!queue.isEmpty())而不先固定 size → 用例[3,9,20,null,null,15,7]，第二层会把 15、7 一起吞进去，输出[[3],[9,20,15,7]]。- 错误写法：内层循环用
for (int i = 0; i < queue.size(); i++)→ 用例同上，队列长度在循环中被孩子撑大，边界随之漂移，分层同样出错。- 错误写法：漏掉根为空的判断 → 用例
root = null，queue.offer(null)之后取node.val直接空指针异常。- 错误写法：判空后返回
null→ 用例root = null，期望输出是[]，返回 null 判错。- 错误写法：孩子入队时不判空 → 用例
[1,null,2]，null 左孩子被塞进队列，下一轮弹出后访问node.val崩溃。- 错误写法：入队顺序写成先右后左 → 用例
[3,9,20,null,null,15,7]，输出变成[[3],[20,9],[7,15]]，层内顺序整个反了。- 错误写法：把本层列表在外层循环之前只 new 一次，每轮复用同一个对象 → 用例
[3,9,20,null,null,15,7]，答案里三个子列表指向同一个引用，最终全部变成最后一层[[15,7],[15,7],[15,7]]。- 错误写法：Java 里用
LinkedList当队列却调用pop()/push()→ 这两个方法操作的是头部，等价于栈语义，用例[3,9,20,null,null,15,7]的遍历顺序会退化成深度优先，分层结果完全错乱。- 错误写法：Go 里在内层循环中一边
queue = queue[1:]裁剪一边用下标queue[i]取值 → 用例[3,9,20,null,null,15,7]，两种访问方式的基准不一致，取到的节点错位甚至越界 panic。- 错误写法：把
res.add(level)写进内层循环 → 用例[3,9,20,null,null,15,7]，每弹出一个节点就追加一次，输出出现大量重复的中间态列表。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 同一模板的英文原题，可作为分层写法的基准 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 需要按层号交替方向，用双端插入避免额外反转 |
| 107. 二叉树的层序遍历 II | 中等 | 结果自底向上，用头插或最后整体反转 |
| 199. 二叉树的右视图 | 中等 | 每层只取最后一个节点，考察层内下标判断 |
| 429. N 叉树的层序遍历 | 中等 | 孩子数不固定，入队要遍历 children 列表 |
| 513. 找树左下角的值 | 中等 | 只需最后一层的首元素，可改成先右后左入队后取末位 |
| 515. 在每个树行中找最大值 | 中等 | 层内做聚合而非收集，注意初值取 Integer.MIN_VALUE
|
| 637. 二叉树的层平均值 | 简单 | 层内求和后除以 size，需用 long 或 double 防溢出 |
| 662. 二叉树最大宽度 | 中等 | 要给节点编号并处理空位，编号需减去层首偏移防溢出 |
| 958. 二叉树的完全性检验 | 中等 | 空节点也入队，一旦出现空之后再遇非空即判否 |
| 1302. 层数最深叶子节点的和 | 中等 | 只保留最后一层的和，每层直接覆盖上一层结果 |
| LCR 044. 在每个树行中找最大值 | 中等 | 515 的中文版，适合练层内聚合的边界初值 |
| LCR 045. 找树左下角的值 | 中等 | 513 的中文版，考察最深层左端点的定位 |
| LCR 046. 二叉树的右视图 | 中等 | 199 的中文版，可对照 DFS 按深度首次访问的写法 |
| 剑指 Offer 32 - I. 从上到下打印二叉树 | 中等 | 输出一维数组，不需要分层，可省掉 size 快照 |
| 剑指 Offer 32 - III. 从上到下打印二叉树 III | 中等 | 之字形输出，考察奇偶层的方向切换 |
| 面试题 04.03. 特定深度节点链表 | 中等 | 每层要串成链表返回，需在层内维护尾指针 |