尧图网站建设 
LeetCode-Book 精讲LCR 150 彩灯装饰记录 II——用队列实现二叉树逐层分行打印【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇基于 LeetCode-Book 仓库中的 《LCR 150. 彩灯装饰记录 II》 文档展开讲解如何在二叉树的广度优先遍历BFS基础上实现每层打印到一行的按层分组输出。你将掌握队列的长度快照技巧、for循环固定层节点数的方法以及 Python / Java / C 三种语言的完整可运行实现并了解它与仓库中 LCR 149、LCR 151 两道姊妹题的区别。题目回顾从按层打印到每层一行本题是剑指 Offer 专项突击版中的二叉树层序遍历进阶题对应 LeetCode 第 102 题二叉树的层序遍历请实现一个函数按照之字形顺序打印二叉树即第一行按照从左到右的顺序打印……本题从上到下打印二叉树每一层打印到一行返回ListListint类型的结果。它与前一道题 LCR 149. 彩灯装饰记录 I普通层序遍历结果为一维数组的区别在于LCR 149 将整棵树的所有节点打平成一个一维数组输出而 LCR 150 要求把每一层的节点单独放入一行最终返回一个二维数组。在仓库源码中LCR 149 对应的是不分组的一维输出List[int]/int[]/vectorint而本题对应分组后的二维输出ListListInteger/vectorvectorint。核心思路BFS 队列 层长快照二叉树的层序遍历本质上就是广度优先遍历BFS通常借助队列的**先入先出FIFO**特性实现根节点先入队出队时打印同时将其左右子节点入队如此循环直到队列为空。但普通 BFS 循环只会给出一个平铺的节点序列如何知道哪些节点属于同一层关键在于一个精妙的技巧在进入每一层之前先记录队列当前的节点数即当前层节点数然后让本轮for循环恰好执行这么多次。由于 BFS 是按层推进的循环开始时队列中的节点正好全部属于同一层本轮循环只处理这些节点出队、打印、把它们的子节点入队新入队的子节点属于下一层留到下一轮循环处理。这样每轮循环恰好消化一层tmp列表中收集的就是这一层的全部节点值。算法流程特例处理当根节点为空直接返回空列表[]初始化打印结果列表res []包含根节点的队列queue [root]BFS 循环当队列queue为空时跳出新建临时列表tmp用于存储当前层打印结果当前层打印循环循环次数为当前层节点数即队列queue的长度出队队首元素出队记为node打印将node.val添加至tmp尾部添加子节点若node的左右子节点不为空则将左右子节点加入队列queue将当前层结果tmp添加入res返回值返回打印结果列表res。其中第 3.2 步的循环次数固定是实现分行的关键循环开始前先取len(queue)存入循环条件循环体内即使不断有新节点入队本轮也只会处理固定数量的节点从而保证一层一处理、一行一输出。三种语言实现Python 实现class Solution: def decorateRecord(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) return resPython 中使用collections中的双端队列deque()其popleft()方法可达到O(1) 时间复杂度而列表 list 的pop(0)方法由于需要整体前移元素时间复杂度为O(N)。因此当队列规模较大时务必使用deque而非 list 充当队列。Java 实现class Solution { public ListListInteger decorateRecord(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; } }Java 中把LinkedList当作队列使用poll()出队、add()入队均满足 FIFO 语义。注意循环条件的写法for(int i queue.size(); i 0; i--)queue.size()只在初始化时求值一次正好锁定当前层节点数之后即使queue.add()改变了队列长度也不影响本轮循环次数。C 实现class Solution { public: vectorvectorint decorateRecord(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 使用标准库std::queueTreeNode*front()获取队首、pop()出队、push()入队。这里复用了形参指针root作为遍历游标先取队首再出队然后打印并把左右孩子入队。复杂度分析时间复杂度 O(N)N 为二叉树的节点数量。每个节点恰好入队、出队各一次BFS 循环总计执行 N 次每层的tmp追加操作也是 O(1)因此总时间为 O(N)。空间复杂度 O(N)最差情况下即当树为平衡二叉树或满二叉树时队列中最多同时存在 N/2 个树节点最底层的全部节点因此需要 O(N) 大小的额外空间结果数组res本身也占用 O(N) 空间。仓库源码印证与运行验证该解法在 LeetCode-Book 仓库的 精选面试题解 目录中有三种语言的同构实现与本题代码几乎一一对应方法名levelOrderPythonlc_102_binary_tree_level_order_traversal.py —— 与本文 Python 解法完全一致使用collections.deque()与for _ in range(len(queue))的层长快照写法Javalc_102_binary_tree_level_order_traversal.java —— 使用LinkedList作为队列for(int i queue.size(); i 0; i--)锁定层节点数Clc_102_binary_tree_level_order_traversal_s1.cpp —— 使用std::queueTreeNode*与for(int i que.size(); i 0; --i)。这些文件都附带了可直接运行的驱动代码与测试用例。例如三种语言均使用同一棵测试二叉树[3, 9, 20, null, null, 15, 7]Python 通过 include 工具集 中的list_to_tree([3, 9, 20, None, None, 15, 7])构造树Java 通过TreeNode.arrToTree(new Integer[]{3, 9, 20, null, null, 15, 7})构造C 通过vectorToTree({3, 9, 20, INT_MAX, INT_MAX, 15, 7})构造用INT_MAX表示空节点。运行后输出为[[3], [9, 20], [15, 7]]可以直观验证每层打印到一行的效果根节点 3 独占第一行第二层 9、20 排在第二行第三层 15、7 排在第三行。姊妹题串联从打平到分行再到之字形本题处于一个递进式的题组中理解三者的差异有助于吃透层序遍历题目输出结构与本题的差异LCR 149. 彩灯装饰记录 I一维数组普通 BFS不分组所有层打平输出LCR 150. 彩灯装饰记录 II本题二维数组在 BFS 基础上按层分组每层一行LCR 151. 彩灯装饰记录 III二维数组在本题基础上增加锯齿/之字形要求奇数层从左到右、偶数层从右到左LCR 151 的解法中方法三层序遍历 倒序正是本题代码的最小改动先按本题逻辑逐层分组再对偶数层执行倒序Python 中tmp[::-1]、Java 中Collections.reverse(tmp)、C 中reverse(tmp.begin(), tmp.end())。从 LCR 149 → 150 → 151 的递进可以看出掌握了队列 层长快照这一核心模板后只需在层内输出顺序上做文章就能演化出各种按层变体。小结模板记忆while queue:外层循环负责逐层推进for _ in range(len(queue)):内层循环借助层长快照恰好处理一层tmp每层新建、收集完即并入res。语言要点Python 用deque.popleft()O(1)而非list.pop(0)O(N)Java / C 在for循环初始化时求值queue.size()即可锁定本层节点数。复杂度时间 O(N)空间 O(N)队列最坏同时容纳 N/2 个节点。举一反三结合 LCR 151 的三种方法双端队列头尾插入、奇偶层逻辑分离、层内倒序可将本模板无缝扩展为之字形层序遍历。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 精讲：LCR 150 彩灯装饰记录 II——用队列实现二叉树逐层分行打印
LeetCode-Book 精讲LCR 150 彩灯装饰记录 II——用队列实现二叉树逐层分行打印【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇基于 LeetCode-Book 仓库中的 《LCR 150. 彩灯装饰记录 II》 文档展开讲解如何在二叉树的广度优先遍历BFS基础上实现每层打印到一行的按层分组输出。你将掌握队列的长度快照技巧、for循环固定层节点数的方法以及 Python / Java / C 三种语言的完整可运行实现并了解它与仓库中 LCR 149、LCR 151 两道姊妹题的区别。题目回顾从按层打印到每层一行本题是剑指 Offer 专项突击版中的二叉树层序遍历进阶题对应 LeetCode 第 102 题二叉树的层序遍历请实现一个函数按照之字形顺序打印二叉树即第一行按照从左到右的顺序打印……本题从上到下打印二叉树每一层打印到一行返回ListListint类型的结果。它与前一道题 LCR 149. 彩灯装饰记录 I普通层序遍历结果为一维数组的区别在于LCR 149 将整棵树的所有节点打平成一个一维数组输出而 LCR 150 要求把每一层的节点单独放入一行最终返回一个二维数组。在仓库源码中LCR 149 对应的是不分组的一维输出List[int]/int[]/vectorint而本题对应分组后的二维输出ListListInteger/vectorvectorint。核心思路BFS 队列 层长快照二叉树的层序遍历本质上就是广度优先遍历BFS通常借助队列的**先入先出FIFO**特性实现根节点先入队出队时打印同时将其左右子节点入队如此循环直到队列为空。但普通 BFS 循环只会给出一个平铺的节点序列如何知道哪些节点属于同一层关键在于一个精妙的技巧在进入每一层之前先记录队列当前的节点数即当前层节点数然后让本轮for循环恰好执行这么多次。由于 BFS 是按层推进的循环开始时队列中的节点正好全部属于同一层本轮循环只处理这些节点出队、打印、把它们的子节点入队新入队的子节点属于下一层留到下一轮循环处理。这样每轮循环恰好消化一层tmp列表中收集的就是这一层的全部节点值。算法流程特例处理当根节点为空直接返回空列表[]初始化打印结果列表res []包含根节点的队列queue [root]BFS 循环当队列queue为空时跳出新建临时列表tmp用于存储当前层打印结果当前层打印循环循环次数为当前层节点数即队列queue的长度出队队首元素出队记为node打印将node.val添加至tmp尾部添加子节点若node的左右子节点不为空则将左右子节点加入队列queue将当前层结果tmp添加入res返回值返回打印结果列表res。其中第 3.2 步的循环次数固定是实现分行的关键循环开始前先取len(queue)存入循环条件循环体内即使不断有新节点入队本轮也只会处理固定数量的节点从而保证一层一处理、一行一输出。三种语言实现Python 实现class Solution: def decorateRecord(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) return resPython 中使用collections中的双端队列deque()其popleft()方法可达到O(1) 时间复杂度而列表 list 的pop(0)方法由于需要整体前移元素时间复杂度为O(N)。因此当队列规模较大时务必使用deque而非 list 充当队列。Java 实现class Solution { public ListListInteger decorateRecord(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; } }Java 中把LinkedList当作队列使用poll()出队、add()入队均满足 FIFO 语义。注意循环条件的写法for(int i queue.size(); i 0; i--)queue.size()只在初始化时求值一次正好锁定当前层节点数之后即使queue.add()改变了队列长度也不影响本轮循环次数。C 实现class Solution { public: vectorvectorint decorateRecord(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 使用标准库std::queueTreeNode*front()获取队首、pop()出队、push()入队。这里复用了形参指针root作为遍历游标先取队首再出队然后打印并把左右孩子入队。复杂度分析时间复杂度 O(N)N 为二叉树的节点数量。每个节点恰好入队、出队各一次BFS 循环总计执行 N 次每层的tmp追加操作也是 O(1)因此总时间为 O(N)。空间复杂度 O(N)最差情况下即当树为平衡二叉树或满二叉树时队列中最多同时存在 N/2 个树节点最底层的全部节点因此需要 O(N) 大小的额外空间结果数组res本身也占用 O(N) 空间。仓库源码印证与运行验证该解法在 LeetCode-Book 仓库的 精选面试题解 目录中有三种语言的同构实现与本题代码几乎一一对应方法名levelOrderPythonlc_102_binary_tree_level_order_traversal.py —— 与本文 Python 解法完全一致使用collections.deque()与for _ in range(len(queue))的层长快照写法Javalc_102_binary_tree_level_order_traversal.java —— 使用LinkedList作为队列for(int i queue.size(); i 0; i--)锁定层节点数Clc_102_binary_tree_level_order_traversal_s1.cpp —— 使用std::queueTreeNode*与for(int i que.size(); i 0; --i)。这些文件都附带了可直接运行的驱动代码与测试用例。例如三种语言均使用同一棵测试二叉树[3, 9, 20, null, null, 15, 7]Python 通过 include 工具集 中的list_to_tree([3, 9, 20, None, None, 15, 7])构造树Java 通过TreeNode.arrToTree(new Integer[]{3, 9, 20, null, null, 15, 7})构造C 通过vectorToTree({3, 9, 20, INT_MAX, INT_MAX, 15, 7})构造用INT_MAX表示空节点。运行后输出为[[3], [9, 20], [15, 7]]可以直观验证每层打印到一行的效果根节点 3 独占第一行第二层 9、20 排在第二行第三层 15、7 排在第三行。姊妹题串联从打平到分行再到之字形本题处于一个递进式的题组中理解三者的差异有助于吃透层序遍历题目输出结构与本题的差异LCR 149. 彩灯装饰记录 I一维数组普通 BFS不分组所有层打平输出LCR 150. 彩灯装饰记录 II本题二维数组在 BFS 基础上按层分组每层一行LCR 151. 彩灯装饰记录 III二维数组在本题基础上增加锯齿/之字形要求奇数层从左到右、偶数层从右到左LCR 151 的解法中方法三层序遍历 倒序正是本题代码的最小改动先按本题逻辑逐层分组再对偶数层执行倒序Python 中tmp[::-1]、Java 中Collections.reverse(tmp)、C 中reverse(tmp.begin(), tmp.end())。从 LCR 149 → 150 → 151 的递进可以看出掌握了队列 层长快照这一核心模板后只需在层内输出顺序上做文章就能演化出各种按层变体。小结模板记忆while queue:外层循环负责逐层推进for _ in range(len(queue)):内层循环借助层长快照恰好处理一层tmp每层新建、收集完即并入res。语言要点Python 用deque.popleft()O(1)而非list.pop(0)O(N)Java / C 在for循环初始化时求值queue.size()即可锁定本层节点数。复杂度时间 O(N)空间 O(N)队列最坏同时容纳 N/2 个节点。举一反三结合 LCR 151 的三种方法双端队列头尾插入、奇偶层逻辑分离、层内倒序可将本模板无缝扩展为之字形层序遍历。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考