剑指 Offer 32-II:从上到下打印二叉树 II —— 基于队列的分层 BFS 实现详解(LeetCode-Book)
剑指 Offer 32-II:从上到下打印二叉树 II —— 基于队列的分层 BFS 实现详解(LeetCode-Book)
本篇以《剑指 Offer》题库中的"剑指 Offer 32 - II. 从上到下打印二叉树 II"为核心,讲清"每层打印到一行"的分层广度优先搜索(BFS)思路:从算法流程、逐层循环的关键技巧,到 Python / Java / C++ 三种语言在 LeetCode-Book 仓库中的完整实现代码与配套测试脚手架,最后给出复杂度分析,帮助读者掌握二叉树层序遍历这一高频面试考点的完整解法。
题目定位:与 32-I、32-III 的关系
本题在仓库文档中的原始表述为:
建议先做 剑指 Offer 32 - I. 从上到下打印二叉树 再做此题,两题仅有微小区别,即本题需将每一层打印到一行。
仓库中同一系列共三题,可按难度递进刷:
| 题目 | 输出要求 | 对应解题代码 |
|---|---|---|
| 32 - I | 所有节点值打印到一个列表中 | sfo_32i_print_a_binary_tree_topbottom_i_s1.py |
| 32 - II(本篇) | 每一层打印到一行(List<a href="https://link.gitcode.com/i/f4d2c961d3dc8a8d1c56990f8b71e9f5" target="_blank">List[int]]) |
[sfo_32ii_print_a_binary_tree_topbottom_ii_s1.py |
| 32 - III | 锯齿形(之字形)层序遍历 | sfo_32iii_print_a_binary_tree_topbottom_iii_s1.py |
两题的核心差异仅在于结果的组织方式:32-I 是单层平铺的 List[int],32-II 是二维结构 List[List[int]]。理解了这个差异,本文的解法就是在 32-I 的基础上"套一层按层循环"。
解题思路:BFS + 固定层大小的双重循环
I. 按层打印: 题目要求的二叉树的从上至下打印(即按层打印),又称为二叉树的广度优先搜索(BFS)。BFS 通常借助队列的先入先出特性来实现。
II. 每层打印到一行: 将本层全部节点打印到一行,并将下一层全部节点加入队列,以此类推,即可分为多行打印。
算法流程
- 特例处理: 当根节点为空,则返回空列表
[]; - 初始化: 打印结果列表
res = [],包含根节点的队列queue = [root]; - BFS 循环: 当队列
queue为空时跳出;- 新建一个临时列表
tmp,用于存储当前层打印结果; - 当前层打印循环: 循环次数为当前层节点数(即队列
queue长度);- 出队: 队首元素出队,记为
node; - 打印: 将
node.val添加至tmp尾部; - 添加子节点: 若
node的左(右)子节点不为空,则将左(右)子节点加入队列queue;
- 出队: 队首元素出队,记为
- 将当前层结果
tmp添加入res。
- 新建一个临时列表
- 返回值: 返回打印结果列表
res。
关键在于内层循环的边界:for _ in range(len(queue))(或 C++/Java 中 for (int i = que.size(); i > 0; --i))在进入内层前一次性读取了当前层的节点数。内层循环中虽然会不断向队尾追加下一层子节点,但循环次数已被锁定,因此循环结束时队列中恰好只剩下一层节点——这正是"层与层之间天然隔离"的机制,无需显式记录层号或插入分隔符。
Python 实现:deque 保证 O(1) 出队
文档特别强调:Python 中使用 collections 中的双端队列 deque(),其 popleft() 方法可达到 O(1) 时间复杂度;列表 list 的 pop(0) 方法时间复杂度为 O(N),因此队列实现不能偷懒用普通列表。
仓库中的实现(sfo_32ii_print_a_binary_tree_topbottom_ii_s1.py):
# ===== Solution Code =====
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)): # 固定当前层节点数
node = queue.popleft()
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp) # 整层结果入 res
return res
对比 32-I 的实现(sfo_32i_print_a_binary_tree_topbottom_i_s1.py),32-II 只是在外层 while 里增加了"每轮先快照 len(queue)、内层循环结束后 res.append(tmp)"这三处改动,返回类型也从 List[int] 变为 List[List[int]]。
仓库配套的测试脚手架
该文件底部附带可直接运行的测试驱动:
# ======= Test Case =======
root = list_to_tree([3, 9, 20, None, None, 15, 7, None, None, None, None])
# ====== Driver Code ======
slt = Solution()
res = slt.levelOrder(root)
print_matrix(res)
其中 list_to_tree 来自公共工具模块 binary_tree.py,它按层序数组语义用 BFS 把列表还原为二叉树:根节点取 arr[0],随后用 deque 依次弹出节点并配对挂上左右孩子;None 表示空位,但仍占位计数。测试用例 [3, 9, 20, None, None, 15, 7, ...] 对应的树形为:
3
/ \
9 20
/ \
15 7
预期输出为 <a href="https://link.gitcode.com/i/6543e54f54d46d388b4b522133a3a84d" target="_blank">[3], [9, 20], [15, 7]]。该文件通过 from include import *(见 [include/__init__.py)统一引入 TreeNode、list_to_tree 与 print_matrix 等工具,保证三题代码风格一致。
Java 实现:用循环计数器锁定层大小
仓库实现(sfo_32ii_print_a_binary_tree_topbottom_ii_s1.java):
// ===== Solution Code =====
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if (root != null)
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for (int i = queue.size(); i > 0; i--) { // 进入内层前快照层大小
TreeNode node = queue.poll();
tmp.add(node.val);
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
两个值得注意的细节:
for (int i = queue.size(); i > 0; i--):queue.size()作为循环上界在for初始化阶段只求值一次,等价于 Python 的range(len(queue)),是 Java 写法中最简洁的"层边界"技巧(LinkedList实现Queue时poll()为 O(1));- 空树处理前置:
if (root != null) queue.add(root)把根节点入队放在判空内,因此空树时while循环一次都不执行,直接返回空res,与文档"特例处理返回空列表"一致。
文件末尾的 main 方法与 Python 版使用同一组测试用例:TreeNode.arrToTree(new Integer<a href="https://link.gitcode.com/i/9bbaa60aeae1b9a9e8c856a7fe4e2356" target="_blank">] {3, 9, 20, null, null, 15, 7, null, null, null, null}),并用 Arrays.deepToString(res.toArray()) 打印二维结果。其中 TreeNode.arrToTree 定义在公共类 [TreeNode.java 中,与 Python 侧的 list_to_tree 语义一致。
C++ 实现:queue 与 vector 的经典组合
仓库实现(sfo_32ii_print_a_binary_tree_topbottom_ii_s1.cpp):
// ===== Solution Code =====
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode *root) {
queue<TreeNode *> que;
vector<vector<int>> res;
if (root != NULL)
que.push(root);
while (!que.empty()) {
vector<int> tmp;
for (int i = que.size(); i > 0; --i) { // 快照层大小
root = que.front();
que.pop();
tmp.push_back(root->val);
if (root->left != NULL)
que.push(root->left);
if (root->right != NULL)
que.push(root->right);
}
res.push_back(tmp);
}
return res;
}
};
与文档版本一致,仓库的 C++ 代码复用入参指针 root 作为出队节点的载体(root = que.front(); que.pop();),避免了额外声明临时指针变量。测试驱动使用 vectorToTree(vector<int>{3, 9, 20, INT_MAX, INT_MAX, 15, 7, ...}) 构造同一棵树——由于 C++ 侧无法在 vector<int> 中表达 nullptr,仓库约定用 INT_MAX 作为空节点哨兵值,这一点在 include.hpp 对应的工具函数中实现,阅读时不要误以为是题目数据的一部分。
三种语言的解法在结构上完全同构:特判空树 → 根入队 → 外层 while + 内层 for(快照层大小)→ 每轮收集 tmp 并追加子节点 → 层结束并入 res。
复杂度分析
- 时间复杂度 O(N): N 为二叉树节点数量,即 BFS 需循环 N 次。每个节点恰好入队一次、出队一次,每次出队伴随 O(1) 的入队子节点操作,因此总耗时与节点数线性相关;
- 空间复杂度 O(N): 最差情况下,即当树为平衡二叉树时,最多有 N/2 个树节点同时在
queue中(即最后一层全部节点已入队而尚未出队的时刻),使用 O(N) 大小的额外空间。若树退化为链状(每个节点只有一个孩子),则队列最多只有 1 个节点,空间降为 O(1);Python 实现中res本身也保存全部节点值,同样占 O(N)。
小结与延伸
- 本题的"分层"技巧完全来自内层循环前对队列长度取快照,这一模式同时适用于 32-II(分层输出)与 32-III(锯齿形只需在奇数层对
tmp反转); - 语言实现差异集中在队列工具的选择:Python 必须用
collections.deque的popleft()获得 O(1) 出队,Java 用LinkedList作为Queue,C++ 用标准库queue<T>(底层同样是双端队列); - 三题的完整对照实现可在仓库中交叉阅读:32-I 文档、32-III 文档,以及
sword_for_offer/codes/下python、java、cpp三个目录中对应的sfo_32*代码文件,均附带可独立运行的测试用例,便于本地验证。