二叉树的层序遍历 II

记住「正常 BFS 按层收 → 最后整层倒序」,下面逐帧套它。注意每层是整层一起收下,再去找下一层。

什么是层：先找感觉:同一深度的节点属于同一层。根 3 是第 0 层,它的孩子 9、20 是第 1 层,再往下 15、7 是第 2 层。BFS 正是一层接一层地访问。

第 0 层就位：进入第 0 层,队列里是 [3]。这一层先整层收下,再去找它们的孩子组成下一层。

第 0 层 · 收值：从队首取出 3(标红),把它的值收进第 0 层的列表,现在本层是 [3]。

第 0 层 · 收孩子：3 处理完(变绿)。把它的非空孩子 9、20(蓝色)加入下一层,目前下一层攒到了 [9、20]。

第 0 层收齐：第 0 层整层收齐 = [3]。下一层 [9、20] 已就绪,继续往下。

第 1 层就位：进入第 1 层,队列里是 [9、20]。这一层先整层收下,再去找它们的孩子组成下一层。

第 1 层 · 收值：从队首取出 9(标红),把它的值收进第 1 层的列表,现在本层是 [9]。

第 1 层 · 收孩子：9 是叶子,没有孩子可加(变绿),下一层暂时还是 [空]。

第 1 层 · 收值：从队首取出 20(标红),把它的值收进第 1 层的列表,现在本层是 [9、20]。

第 1 层 · 收孩子：20 处理完(变绿)。把它的非空孩子 15、7(蓝色)加入下一层,目前下一层攒到了 [15、7]。

第 1 层收齐：第 1 层整层收齐 = [9、20]。下一层 [15、7] 已就绪,继续往下。

第 2 层就位：进入第 2 层,队列里是 [15、7]。这一层先整层收下,再去找它们的孩子组成下一层。

第 2 层 · 收值：从队首取出 15(标红),把它的值收进第 2 层的列表,现在本层是 [15]。

第 2 层 · 收孩子：15 是叶子,没有孩子可加(变绿),下一层暂时还是 [空]。

第 2 层 · 收值：从队首取出 7(标红),把它的值收进第 2 层的列表,现在本层是 [15、7]。

第 2 层 · 收孩子：7 是叶子,没有孩子可加(变绿),下一层暂时还是 [空]。

第 2 层收齐：第 2 层整层收齐 = [15、7]。没有下一层了,BFS 即将结束。

BFS 收集完成：队列空了,BFS 结束。自顶向下收集到 [[3], [9,20], [15,7]]。但题目要的是自底向上,所以最后把这些层整体倒过来。

倒序 · 第 1 层落位：倒序第 1 步:把原来的第 2 层 [15、7](高亮)放到结果里。现在自底向上结果是 [[15,7]]。

倒序 · 第 2 层落位：倒序第 2 步:把原来的第 1 层 [9、20](高亮)放到结果里。现在自底向上结果是 [[15,7], [9,20]]。

倒序 · 第 3 层落位：倒序第 3 步:把原来的第 0 层 [3](高亮)放到结果里。现在自底向上结果是 [[15,7], [9,20], [3]]。

完成：自底向上的层序遍历就是 [[15,7], [9,20], [3]]:最底层 [15、7] 排最前,根 [3] 在最后。回头看,就是一遍正常 BFS 按层收集,末尾整体倒序,时间 O(n)。

边界:空树返回空、单节点一层、链每层一个节点。

两个追问:头插可免末尾反转;BFS 按层框架能解一大类「按层」问题。