LeetCode-Book 题解：LCR 149 彩灯装饰记录 I——用队列实现二叉树层序遍历（BFS）实战指南

LeetCode-Book 题解：LCR 149 彩灯装饰记录 I——用队列实现二叉树层序遍历（BFS）实战指南

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

导读

本篇技术指南以《LeetCode-Book》仓库中 LCR 149. 彩灯装饰记录 I 题解文档为核心，系统讲解二叉树的**层序遍历（广度优先遍历，BFS）**的完整解法：从算法流程、Python / Java / C++ 三语言实现，到队列数据结构的选型原理与时空复杂度分析。同时结合仓库sword_for_offer/codes下同题对应源码（剑指 Offer 32 - I）印证实现细节，并串联 LCR 150、LCR 151 两道进阶题目，帮助读者真正吃透"用队列做层序遍历"这一面试高频考点。

题目背景：什么是"彩灯装饰记录 I"

LCR 149「彩灯装饰记录 I」是《图解算法数据结构》（leetbook_ioa）中二叉树模块的经典入门题，其本质是按层从左到右打印二叉树所有节点的值，与经典题 102. 二叉树的层序遍历 以及《剑指 Offer》32 - I「从上到下打印二叉树」完全同源（仓库中对应实现见下文源码链接）。

题目要求输出的是一维数组（List[int]），即把所有节点按"先上层后下层、同层从左到右"的顺序排列。示例树[3, 9, 20, null, null, 15, 7]的输出应为[3, 9, 20, 15, 7]。

核心解题思路：BFS + 队列的先入先出特性

题目要求按层打印二叉树，这恰好对应二叉树的广度优先遍历。BFS 的逐层推进特性，天然依赖队列的"先入先出"（FIFO）机制：

• 父节点出队时，将其左、右子节点依次追加到队尾；
• 由于队列先进先出，先入队的上一层节点必然先被访问，从而保证"从左到右、从上到下"的输出顺序。

正是借助队列"先进先出、逐层接力"的特性，BFS 才能以非递归方式完成整棵树的层次访问，这也是该题唯一的推荐解法定式。

算法流程（四步走）

1. 特例处理：若根节点root为空，直接返回空列表[]；
2. 初始化：声明结果列表res = []，并将根节点放入队列queue = [root]；
3. BFS 循环：当队列queue为空时跳出循环，每轮执行：
   • 出队：队首元素出队，记为node；
   • 打印：将node.val追加到结果列表尾部；
   • 添加子节点：若node的左（右）子节点不为空，则将其左（右）子节点加入队列queue；
4. 返回值：返回打印结果列表res。

队列选型的关键细节

• Python：使用collections模块的双端队列deque()，其popleft()方法（队首弹出）时间复杂度为O(1)；
• Java：使用LinkedList实现的Queue接口，poll()弹出队首同样为 O(1)；
• C++：使用标准库std::queue，front()取队首、pop()弹出，均为 O(1)；
• 反例提醒：Python 内置列表list的pop(0)方法需要整体搬移元素，时间复杂度为O(N)，在大数据量下会造成整体退化为 O(N²)，不要用它替代deque。

三语言参考代码

Python 实现

class Solution: def decorateRecord(self, root: TreeNode) -> List[int]: if not root: return [] res, queue = [], collections.deque() queue.append(root) while queue: node = queue.popleft() res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res

Java 实现

class Solution { public int[] decorateRecord(TreeNode root) { if(root == null) return new int[0]; Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }}; ArrayList<Integer> ans = new ArrayList<>(); while(!queue.isEmpty()) { TreeNode node = queue.poll(); ans.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } int[] res = new int[ans.size()]; for(int i = 0; i < ans.size(); i++) res[i] = ans.get(i); return res; } }

Java 版最终返回int[]基本类型数组，因此需要先把结果暂存到ArrayList<Integer>，最后再拷贝为int[]，这一细节在面试手写代码时容易被忽略。

C++ 实现

class Solution { public: vector<int> decorateRecord(TreeNode* root) { vector<int> res; if(!root) return res; queue<TreeNode *> que; que.push(root); while(!que.empty()){ TreeNode* node = que.front(); que.pop(); res.push_back(node->val); if(node->left) que.push(node->left); if(node->right) que.push(node->right); } return res; } };

复杂度分析

• 时间复杂度 O(N)：N 为二叉树节点数量。每个节点恰好出队一次、入队一次，BFS 主循环共执行 N 次，队列的入队 / 出队操作均为 O(1)；
• 空间复杂度 O(N)：队列中最多同时存在树的一整层节点。最差情况下，当二叉树为**平衡二叉树（或满二叉树）**时，最底层约有 N/2 个节点同时驻留队列，故需要 O(N) 级别的额外空间。

仓库源码印证：与剑指 Offer 32 - I 完全同源

在《LeetCode-Book》仓库中，本题与《剑指 Offer》32 - I「从上到下打印二叉树」为同一道题，sword_for_offer/codes下分别提供了三种语言的完整可运行实现（含测试用例与驱动代码），可直接对照验证：

测试用例的构造方式

三个版本使用同一棵示例二叉树，便于跨语言对照运行结果（输出均为3 9 20 15 7）：

# Python：list_to_tree 按层序数组建树 root = list_to_tree([3, 9, 20, None, None, 15, 7, None, None, None, None]) slt = Solution() res = slt.levelOrder(root) print(res)

// Java：TreeNode.arrToTree 按层序数组建树 TreeNode root = TreeNode.arrToTree(new Integer[] { 3, 9, 20, null, null, 15, 7, null, null, null, null });

// C++：vectorToTree 按层序数组建树（INT_MAX 表示空节点） TreeNode *root = vectorToTree(vector<int>{3, 9, 20, INT_MAX, INT_MAX, 15, 7, INT_MAX, INT_MAX, INT_MAX, INT_MAX});

其中list_to_tree、TreeNode.arrToTree、vectorToTree等辅助工具定义在各语言codes目录下的include文件夹中（Python 见 include、Java 见 include、C++ 见 include），这也是本仓库所有树类题目的统一基建，读者可自行翻阅学习建树与打印工具的实现。

驱动代码的运行方式

• Python：sfo_32i_print_a_binary_tree_topbottom_i_s1.py底部自带Driver Code，直接python运行该文件即可打印结果；
• Java：main方法位于sfo_32i_print_a_binary_tree_topbottom_i_s1类中，编译时需带上include包路径；
• C++：main函数内通过PrintUtil::printVector(res)打印结果，编译时需将 include.hpp 加入包含路径。

这种"题解文档 + 三语言可运行代码"的配套结构，正是《LeetCode-Book》仓库的核心组织方式：leetbook_ioa/docs提供思路讲解，selected_coding_interview/codes与sword_for_offer/codes提供源码佐证。

由浅入深：LCR 149 是层序遍历系列的"地基"

LCR 149 只要求"按层打印成一维数组"，但它在 leetbook_ioa 的彩灯装饰系列中是承上启下的基础题，同系列进阶题在其骨架上有两处典型变形，读者可将 LCR 149 的代码作为模板直接改造：

1. LCR 150. 彩灯装饰记录 II：要求把每层打印到单独一行（输出List[List[int]]）。核心技巧是：在每轮 BFS 前先记录当前队列长度len(queue)，用for _ in range(len(queue))固定本轮出队次数，从而区分层边界——这也正是仓库中sfo_32ii_print_a_binary_tree_topbottom_ii系列代码的实现思路。

2. LCR 151. 彩灯装饰记录 III：要求按之字形（锯齿形）交替方向打印，仓库给出三种解法（双端队列两端插入、奇偶层逻辑分离、层结果倒序），对应sfo_32iii_print_a_binary_tree_topbottom_iii的 s1/s2/s3 三份实现。

无论题目如何变形，其底层都是 LCR 149 中"队列 FIFO + 逐层出队入队"的 BFS 框架。建议读者先吃透本文的队列写法，再对照 LCR 150 与 LCR 151 逐步升级，即可完整掌握层序遍历的三连问。

小结

• 层序遍历（BFS）的标准实现是队列，核心三动作：队首出队 → 记录节点值 → 左右子节点入队；
• Python 必须用collections.deque().popleft()（O(1)），避开list.pop(0)（O(N)）；
• 时间复杂度 O(N)，空间复杂度 O(N)（平衡树时队列峰值约 N/2）；
• 同题源码可参考仓库sword_for_offer/codes下的sfo_32i三语言实现，含完整测试用例可直接运行；
• 本解法是 LCR 150（按层分组）与 LCR 151（之字形）的公共基础，一题掌握、三题通用。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book