尧图网站建设 
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 两道进阶题目帮助读者真正吃透用队列做层序遍历这一面试高频考点。题目背景什么是彩灯装饰记录 ILCR 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 才能以非递归方式完成整棵树的层次访问这也是该题唯一的推荐解法定式。算法流程四步走特例处理若根节点root为空直接返回空列表[]初始化声明结果列表res []并将根节点放入队列queue [root]BFS 循环当队列queue为空时跳出循环每轮执行出队队首元素出队记为node打印将node.val追加到结果列表尾部添加子节点若node的左右子节点不为空则将其左右子节点加入队列queue返回值返回打印结果列表res。队列选型的关键细节Python使用collections模块的双端队列deque()其popleft()方法队首弹出时间复杂度为O(1)Java使用LinkedList实现的Queue接口poll()弹出队首同样为 O(1)C使用标准库std::queuefront()取队首、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 resJava 实现class Solution { public int[] decorateRecord(TreeNode root) { if(root null) return new int[0]; QueueTreeNode queue new LinkedList(){{ add(root); }}; ArrayListInteger 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[]基本类型数组因此需要先把结果暂存到ArrayListInteger最后再拷贝为int[]这一细节在面试手写代码时容易被忽略。C 实现class Solution { public: vectorint decorateRecord(TreeNode* root) { vectorint res; if(!root) return res; queueTreeNode * 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下分别提供了三种语言的完整可运行实现含测试用例与驱动代码可直接对照验证语言仓库实现路径Pythonsfo_32i_print_a_binary_tree_topbottom_i_s1.pyJavasfo_32i_print_a_binary_tree_topbottom_i_s1.javaCsfo_32i_print_a_binary_tree_topbottom_i_s1.cpp测试用例的构造方式三个版本使用同一棵示例二叉树便于跨语言对照运行结果输出均为3 9 20 15 7# Pythonlist_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)// JavaTreeNode.arrToTree 按层序数组建树 TreeNode root TreeNode.arrToTree(new Integer[] { 3, 9, 20, null, null, 15, 7, null, null, null, null });// CvectorToTree 按层序数组建树INT_MAX 表示空节点 TreeNode *root vectorToTree(vectorint{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这也是本仓库所有树类题目的统一基建读者可自行翻阅学习建树与打印工具的实现。驱动代码的运行方式Pythonsfo_32i_print_a_binary_tree_topbottom_i_s1.py底部自带Driver Code直接python运行该文件即可打印结果Javamain方法位于sfo_32i_print_a_binary_tree_topbottom_i_s1类中编译时需带上include包路径Cmain函数内通过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 的代码作为模板直接改造LCR 150. 彩灯装饰记录 II要求把每层打印到单独一行输出List[List[int]]。核心技巧是在每轮 BFS 前先记录当前队列长度len(queue)用for _ in range(len(queue))固定本轮出队次数从而区分层边界——这也正是仓库中sfo_32ii_print_a_binary_tree_topbottom_ii系列代码的实现思路。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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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 两道进阶题目帮助读者真正吃透用队列做层序遍历这一面试高频考点。题目背景什么是彩灯装饰记录 ILCR 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 才能以非递归方式完成整棵树的层次访问这也是该题唯一的推荐解法定式。算法流程四步走特例处理若根节点root为空直接返回空列表[]初始化声明结果列表res []并将根节点放入队列queue [root]BFS 循环当队列queue为空时跳出循环每轮执行出队队首元素出队记为node打印将node.val追加到结果列表尾部添加子节点若node的左右子节点不为空则将其左右子节点加入队列queue返回值返回打印结果列表res。队列选型的关键细节Python使用collections模块的双端队列deque()其popleft()方法队首弹出时间复杂度为O(1)Java使用LinkedList实现的Queue接口poll()弹出队首同样为 O(1)C使用标准库std::queuefront()取队首、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 resJava 实现class Solution { public int[] decorateRecord(TreeNode root) { if(root null) return new int[0]; QueueTreeNode queue new LinkedList(){{ add(root); }}; ArrayListInteger 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[]基本类型数组因此需要先把结果暂存到ArrayListInteger最后再拷贝为int[]这一细节在面试手写代码时容易被忽略。C 实现class Solution { public: vectorint decorateRecord(TreeNode* root) { vectorint res; if(!root) return res; queueTreeNode * 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下分别提供了三种语言的完整可运行实现含测试用例与驱动代码可直接对照验证语言仓库实现路径Pythonsfo_32i_print_a_binary_tree_topbottom_i_s1.pyJavasfo_32i_print_a_binary_tree_topbottom_i_s1.javaCsfo_32i_print_a_binary_tree_topbottom_i_s1.cpp测试用例的构造方式三个版本使用同一棵示例二叉树便于跨语言对照运行结果输出均为3 9 20 15 7# Pythonlist_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)// JavaTreeNode.arrToTree 按层序数组建树 TreeNode root TreeNode.arrToTree(new Integer[] { 3, 9, 20, null, null, 15, 7, null, null, null, null });// CvectorToTree 按层序数组建树INT_MAX 表示空节点 TreeNode *root vectorToTree(vectorint{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这也是本仓库所有树类题目的统一基建读者可自行翻阅学习建树与打印工具的实现。驱动代码的运行方式Pythonsfo_32i_print_a_binary_tree_topbottom_i_s1.py底部自带Driver Code直接python运行该文件即可打印结果Javamain方法位于sfo_32i_print_a_binary_tree_topbottom_i_s1类中编译时需带上include包路径Cmain函数内通过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 的代码作为模板直接改造LCR 150. 彩灯装饰记录 II要求把每层打印到单独一行输出List[List[int]]。核心技巧是在每轮 BFS 前先记录当前队列长度len(queue)用for _ in range(len(queue))固定本轮出队次数从而区分层边界——这也正是仓库中sfo_32ii_print_a_binary_tree_topbottom_ii系列代码的实现思路。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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考