剑指 Offer 32-II从上到下打印二叉树 II —— 基于队列的分层 BFS 实现详解LeetCode-Book【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/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.py32 - II本篇每一层打印到一行List[List[int]]sfo_32ii_print_a_binary_tree_topbottom_ii_s1.py32 - 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.py32-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预期输出为[[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 ListListInteger levelOrder(TreeNode root) { QueueTreeNode queue new LinkedList(); ListListInteger res new ArrayList(); if (root ! null) queue.add(root); while (!queue.isEmpty()) { ListInteger 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[] {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: vectorvectorint levelOrder(TreeNode *root) { queueTreeNode * que; vectorvectorint res; if (root ! NULL) que.push(root); while (!que.empty()) { vectorint 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(vectorint{3, 9, 20, INT_MAX, INT_MAX, 15, 7, ...})构造同一棵树——由于 C 侧无法在vectorint中表达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作为QueueC 用标准库queueT底层同样是双端队列三题的完整对照实现可在仓库中交叉阅读32-I 文档、32-III 文档以及sword_for_offer/codes/下python、java、cpp三个目录中对应的sfo_32*代码文件均附带可独立运行的测试用例便于本地验证。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
剑指 Offer 32-II：从上到下打印二叉树 II —— 基于队列的分层 BFS 实现详解（LeetCode-Book）
剑指 Offer 32-II从上到下打印二叉树 II —— 基于队列的分层 BFS 实现详解LeetCode-Book【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/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.py32 - II本篇每一层打印到一行List[List[int]]sfo_32ii_print_a_binary_tree_topbottom_ii_s1.py32 - 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.py32-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预期输出为[[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 ListListInteger levelOrder(TreeNode root) { QueueTreeNode queue new LinkedList(); ListListInteger res new ArrayList(); if (root ! null) queue.add(root); while (!queue.isEmpty()) { ListInteger 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[] {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: vectorvectorint levelOrder(TreeNode *root) { queueTreeNode * que; vectorvectorint res; if (root ! NULL) que.push(root); while (!que.empty()) { vectorint 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(vectorint{3, 9, 20, INT_MAX, INT_MAX, 15, 7, ...})构造同一棵树——由于 C 侧无法在vectorint中表达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作为QueueC 用标准库queueT底层同样是双端队列三题的完整对照实现可在仓库中交叉阅读32-I 文档、32-III 文档以及sword_for_offer/codes/下python、java、cpp三个目录中对应的sfo_32*代码文件均附带可独立运行的测试用例便于本地验证。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
