剑指 Offer 32-II:从上到下打印二叉树 II —— 基于队列的分层 BFS 实现详解(LeetCode-Book)

原创2026-09-15 10:40:121,941 阅读
文章标签:教育教程

剑指 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. 每层打印到一行: 将本层全部节点打印到一行,并将下一层全部节点加入队列,以此类推,即可分为多行打印。

算法流程

  1. 特例处理: 当根节点为空,则返回空列表 [];
  2. 初始化: 打印结果列表 res = [],包含根节点的队列 queue = [root];
  3. BFS 循环: 当队列 queue 为空时跳出;
    1. 新建一个临时列表 tmp,用于存储当前层打印结果;
    2. 当前层打印循环: 循环次数为当前层节点数(即队列 queue 长度);
      1. 出队: 队首元素出队,记为 node;
      2. 打印: 将 node.val 添加至 tmp 尾部;
      3. 添加子节点: 若 node 的左(右)子节点不为空,则将左(右)子节点加入队列 queue;
    3. 将当前层结果 tmp 添加入 res。
  4. 返回值: 返回打印结果列表 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* 代码文件,均附带可独立运行的测试用例,便于本地验证。
登录后查看全文
LeetCode-Book