LeetCode-Book 精讲LCR 151 彩灯装饰记录 III二叉树锯齿形层序遍历双端队列三解法【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南以 LeetCode-Book 仓库中《LCR 151. 彩灯装饰记录 III》文档为核心系统讲解二叉树锯齿形层序遍历奇偶层交替正反向打印的三种解法层序遍历 双端队列、奇偶层逻辑分离、层序遍历 倒序。结合仓库内 剑指 Offer 32 - III 的 Python 源码 与测试驱动代码读者可完整掌握 BFS 层序遍历的变形技巧、双端队列两端操作的 $O(1)$ 复杂度优势以及三种解法的复杂度权衡。题目背景从从上到下打印二叉树到锯齿形遍历LCR 151「彩灯装饰记录 III」是剑指 Offer 32 系列题目的第三问对应经典力扣题 103「二叉树的锯齿形层序遍历」。它与同系列题目的关系如下LCR 149剑指 Offer 32 - I从上到下打印二叉树输出一维数组LCR 150剑指 Offer 32 - II按层打印二叉树输出二维数组LCR 151剑指 Offer 32 - III在按层打印基础上奇数层从左向右、偶数层从右向左打印输出之字形锯齿形结果。本题的核心约束在于同一层节点仍按从左到右的 BFS 顺序入队但输出时偶数层需要反向。三种解法本质都是标准 BFS 层序遍历 层内输出顺序控制区别只在于控制手段双端队列两端插入、奇偶层逻辑分离、输出后倒序。方法一层序遍历 双端队列奇偶层统一判断核心思路利用双端队列两端皆可添加元素的特性设打印列表双端队列tmp并规定奇数层将节点值添加至tmp尾部偶数层将节点值添加至tmp头部。这样在层内从左到右出队的同时偶数层因为后出队的节点值插到头部最终tmp呈现从右到左的顺序恰好完成锯齿形输出。算法流程特例处理当树的根节点为空则直接返回空列表[]初始化打印结果空列表res包含根节点的双端队列dequeBFS 循环当deque为空时跳出新建列表tmp用于临时存储当前层打印结果当前层打印循环循环次数为当前层节点数即deque长度出队队首元素出队记为node打印若为奇数层将node.val添加至tmp尾部否则添加至tmp头部添加子节点若node的左右子节点不为空则加入deque将当前层结果tmp转化为 list 并添加入res返回值返回打印结果列表res。三种语言实现class Solution: def decorateRecord(self, root: TreeNode) - List[List[int]]: if not root: return [] res, deque [], collections.deque([root]) while deque: tmp collections.deque() for _ in range(len(deque)): node deque.popleft() if len(res) % 2 0: tmp.append(node.val) # 奇数层 - 插入队列尾部 else: tmp.appendleft(node.val) # 偶数层 - 插入队列头部 if node.left: deque.append(node.left) if node.right: deque.append(node.right) res.append(list(tmp)) return resclass Solution { public ListListInteger decorateRecord(TreeNode root) { QueueTreeNode queue new LinkedList(); ListListInteger res new ArrayList(); if(root ! null) queue.add(root); while(!queue.isEmpty()) { LinkedListInteger tmp new LinkedList(); for(int i queue.size(); i 0; i--) { TreeNode node queue.poll(); if(res.size() % 2 0) tmp.addLast(node.val); else tmp.addFirst(node.val); if(node.left ! null) queue.add(node.left); if(node.right ! null) queue.add(node.right); } res.add(tmp); } return res; } }class Solution { public: vectorvectorint decorateRecord(TreeNode* root) { dequeTreeNode* deque; vectorvectorint res; if(root ! NULL) deque.push_back(root); while(!deque.empty()) { dequeint tmp; // 注意此处示意为存储 int 的双端队列 ... } } };说明方法一在 Python 与 Java 中可直接用双端队列tmp承接结果C 实现若使用std::dequeint承接层内结果同样能在队头/队尾以 $O(1)$ 复杂度插入。语言要点Python使用collections中的双端队列deque()其popleft()方法可达到 $O(1)$ 时间复杂度而列表 list 的pop(0)方法时间复杂度为 $O(N)$因此本题必须用双端队列做 BFS 队列。Java将链表LinkedList作为双端队列使用addFirst/addLast均为 $O(1)$。复杂度分析时间复杂度 $O(N)$$N$ 为二叉树的节点数量BFS 需循环 $N$ 次占用 $O(N)$双端队列的队首和队尾的添加和删除操作的时间复杂度均为 $O(1)$。空间复杂度 $O(N)$最差情况下即当树为满二叉树时最多有 $N/2$ 个树节点同时在deque中使用 $O(N)$ 大小的额外空间。方法二层序遍历 双端队列奇偶层逻辑分离核心思路与改进点方法一代码简短、容易实现但需要判断每个节点的所在层奇偶性即冗余了 $N$ 次判断。通过将奇偶层逻辑拆分可以消除冗余的判断——奇数层和偶数层各自拥有独立的出队方向与入队方向两个循环交替执行。算法流程与方法一对比仅 BFS 循环不同。BFS 循环循环打印奇 / 偶数层当deque为空时跳出打印奇数层从左向右打印先左后右加入下层节点若deque为空说明向下无偶数层则跳出打印偶数层从右向左打印先右后左加入下层节点。这里的精髓在于偶数层从deque的尾部出队pop()同时把子节点按先右后左的顺序appendleft到队头。这样出队的顺序天然是右→左且入队的子节点顺序恰好保证下一轮奇数层从左向右读取时仍然是先左后右。代码class Solution: def decorateRecord(self, root: TreeNode) - List[List[int]]: if not root: return [] res, deque [], collections.deque() deque.append(root) while deque: tmp [] # 打印奇数层 for _ in range(len(deque)): # 从左向右打印 node deque.popleft() tmp.append(node.val) # 先左后右加入下层节点 if node.left: deque.append(node.left) if node.right: deque.append(node.right) res.append(tmp) if not deque: break # 若为空则提前跳出 # 打印偶数层 tmp [] for _ in range(len(deque)): # 从右向左打印 node deque.pop() tmp.append(node.val) # 先右后左加入下层节点 if node.right: deque.appendleft(node.right) if node.left: deque.appendleft(node.left) res.append(tmp) return resclass Solution { public ListListInteger decorateRecord(TreeNode root) { DequeTreeNode deque new LinkedList(); ListListInteger res new ArrayList(); if(root ! null) deque.add(root); while(!deque.isEmpty()) { // 打印奇数层 ListInteger tmp new ArrayList(); for(int i deque.size(); i 0; i--) { // 从左向右打印 TreeNode node deque.removeFirst(); tmp.add(node.val); // 先左后右加入下层节点 if(node.left ! null) deque.addLast(node.left); if(node.right ! null) deque.addLast(node.right); } res.add(tmp); if(deque.isEmpty()) break; // 若为空则提前跳出 // 打印偶数层 tmp new ArrayList(); for(int i deque.size(); i 0; i--) { // 从右向左打印 TreeNode node deque.removeLast(); tmp.add(node.val); // 先右后左加入下层节点 if(node.right ! null) deque.addFirst(node.right); if(node.left ! null) deque.addFirst(node.left); } res.add(tmp); } return res; } }class Solution { public: vectorvectorint decorateRecord(TreeNode* root) { dequeTreeNode* deque; vectorvectorint res; if(root ! NULL) deque.push_back(root); while(!deque.empty()) { // 打印奇数层 vectorint tmp; for(int i deque.size(); i 0; i--) { // 从左向右打印 TreeNode* node deque.front(); deque.pop_front(); tmp.push_back(node-val); // 先左后右加入下层节点 if(node-left ! NULL) deque.push_back(node-left); if(node-right ! NULL) deque.push_back(node-right); } res.push_back(tmp); if(deque.empty()) break; // 若为空则提前跳出 // 打印偶数层 tmp.clear(); for(int i deque.size(); i 0; i--) { // 从右向左打印 TreeNode* node deque.back(); deque.pop_back(); tmp.push_back(node-val); // 先右后左加入下层节点 if(node-right ! NULL) deque.push_front(node-right); if(node-left ! NULL) deque.push_front(node-left); } res.push_back(tmp); } return res; } };复杂度分析时间复杂度 $O(N)$同方法一但省去了每层节点逐一判断奇偶性的 $N$ 次分支判断常数因子更小。空间复杂度 $O(N)$同方法一。方法三层序遍历 倒序核心思路此方法的优点是只用普通列表即可无需双端队列等额外数据结构。偶数层倒序若res的长度为奇数说明当前是偶数层则对tmp执行倒序操作。也就是说先完全按标准层序遍历从左到右收集当前层节点输出前判断如果当前是偶数层res.size() % 2 1就把这一层的列表整体翻转。代码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[::-1] if len(res) % 2 else tmp) return resclass 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); } if(res.size() % 2 1) Collections.reverse(tmp); res.add(tmp); } return res; } }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--) { TreeNode* node que.front(); que.pop(); tmp.push_back(node-val); if(node-left ! NULL) que.push(node-left); if(node-right ! NULL) que.push(node-right); } if(res.size() % 2 1) reverse(tmp.begin(), tmp.end()); res.push_back(tmp); } return res; } };复杂度分析时间复杂度 $O(N)$$N$ 为二叉树的节点数量BFS 需循环 $N$ 次占用 $O(N)$共完成少于 $N$ 个节点的倒序操作占用 $O(N)$。空间复杂度 $O(N)$最差情况下即当树为满二叉树时最多有 $N/2$ 个树节点同时在queue中使用 $O(N)$ 大小的额外空间。三方法对比与选型建议对比维度方法一双端队列统一判断方法二奇偶层逻辑分离方法三层序遍历 倒序核心数据结构双端队列deque做 BFS层内结果也用双端队列双端队列deque两端交替出队/入队普通队列queue即可奇偶判断次数每个节点判断一次$N$ 次无需逐节点判断逻辑拆分到两个循环每层判断一次层数次代码简洁度代码最短最容易实现逻辑最清晰代码较长代码最短且最直观额外操作无无偶数层整体倒序$O(N)$ 总量时间复杂度$O(N)$$O(N)$常数因子更小$O(N)$空间复杂度$O(N)$$O(N)$$O(N)$选型建议面试快速作答、追求代码最短 → 方法一或方法三追求常数级性能最优、逻辑自解释 → 方法二若环境不支持双端队列如某些简化实现 → 方法三最稳妥。仓库源码印证与本地运行验证LeetCode-Book 仓库完整收录了本题的三种解法源码均位于 sword_for_offer/codes/python/ 目录下与文档一一对应sfo_32iii_print_a_binary_tree_topbottom_iii_s1.py对应方法一层序遍历 双端队列统一判断sfo_32iii_print_a_binary_tree_topbottom_iii_s2.py对应方法二奇偶层逻辑分离sfo_32iii_print_a_binary_tree_topbottom_iii_s3.py对应方法三层序遍历 倒序。这三份源码与文档中的 Python 解法代码完全一致仓库版本将方法名写作levelOrder并内置了完整的测试驱动代码可在本地直接运行验证。仓库测试脚手架以 sfo_32iii_print_a_binary_tree_topbottom_iii_s1.py 为例其结构为from include import * # Solution Code class Solution: def levelOrder(self, root: TreeNode) - 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)其中两个关键工具来自仓库的 include 工具包list_to_tree(arr)定义在 binary_tree.py按层序遍历序列None表示空节点构建二叉树内部同样用collections.deque做 BFS 建树print_matrix(mat)定义在 print_util.py将二维结果按矩阵形式格式化打印。测试用例使用[3, 9, 20, None, None, 15, 7]这棵标准满二叉树根 3左 9、右 2020 的左 15、右 7预期输出为锯齿形结果[[3], [20, 9], [15, 7]]。在仓库的sword_for_offer/codes/python/目录下直接执行python sfo_32iii_print_a_binary_tree_topbottom_iii_s1.py python sfo_32iii_print_a_binary_tree_topbottom_iii_s2.py python sfo_32iii_print_a_binary_tree_topbottom_iii_s3.py三个脚本将分别输出一致的锯齿形层序结果可直观验证三种解法正确性。跨语言一致性与 Python 源码对应仓库在 sword_for_offer/codes/java/sfo_32iii_print_a_binary_tree_topbottom_iii_s1/ 与 sword_for_offer/codes/cpp/sfo_32iii_print_a_binary_tree_topbottom_iii_s1/ 等目录中收录了同题的 Java / C 实现解题思路与本文三方法一一对应适合对照学习多语言写法。此外本题的经典版本还收录于《Krahets 笔面试精选 88 题》的 lc_103 锯齿形层序遍历三版源码对应 文档说明锯齿形遍历是 BFS 家族的常考变形值得反复练习。总结LCR 151「彩灯装饰记录 III」考查的是 BFS 层序遍历的变形能力。三种解法共享同一套 BFS 框架——队列维护待访问节点 按层快照长度切分层次差别仅在偶数层的反向输出手段双端队列头插方法一、双端队列双向出队 反向入队方法二、普通列表输出后整体倒序方法三。三者时间复杂度均为 $O(N)$空间复杂度均为 $O(N)$实践中应优先选择自己最易写对、最易讲清的版本同时理解其余解法的思路以应对面试官关于能否不用双端队列能否去掉逐节点奇偶判断的追问。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 精讲：LCR 151 彩灯装饰记录 III（二叉树锯齿形层序遍历）双端队列三解法
LeetCode-Book 精讲LCR 151 彩灯装饰记录 III二叉树锯齿形层序遍历双端队列三解法【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南以 LeetCode-Book 仓库中《LCR 151. 彩灯装饰记录 III》文档为核心系统讲解二叉树锯齿形层序遍历奇偶层交替正反向打印的三种解法层序遍历 双端队列、奇偶层逻辑分离、层序遍历 倒序。结合仓库内 剑指 Offer 32 - III 的 Python 源码 与测试驱动代码读者可完整掌握 BFS 层序遍历的变形技巧、双端队列两端操作的 $O(1)$ 复杂度优势以及三种解法的复杂度权衡。题目背景从从上到下打印二叉树到锯齿形遍历LCR 151「彩灯装饰记录 III」是剑指 Offer 32 系列题目的第三问对应经典力扣题 103「二叉树的锯齿形层序遍历」。它与同系列题目的关系如下LCR 149剑指 Offer 32 - I从上到下打印二叉树输出一维数组LCR 150剑指 Offer 32 - II按层打印二叉树输出二维数组LCR 151剑指 Offer 32 - III在按层打印基础上奇数层从左向右、偶数层从右向左打印输出之字形锯齿形结果。本题的核心约束在于同一层节点仍按从左到右的 BFS 顺序入队但输出时偶数层需要反向。三种解法本质都是标准 BFS 层序遍历 层内输出顺序控制区别只在于控制手段双端队列两端插入、奇偶层逻辑分离、输出后倒序。方法一层序遍历 双端队列奇偶层统一判断核心思路利用双端队列两端皆可添加元素的特性设打印列表双端队列tmp并规定奇数层将节点值添加至tmp尾部偶数层将节点值添加至tmp头部。这样在层内从左到右出队的同时偶数层因为后出队的节点值插到头部最终tmp呈现从右到左的顺序恰好完成锯齿形输出。算法流程特例处理当树的根节点为空则直接返回空列表[]初始化打印结果空列表res包含根节点的双端队列dequeBFS 循环当deque为空时跳出新建列表tmp用于临时存储当前层打印结果当前层打印循环循环次数为当前层节点数即deque长度出队队首元素出队记为node打印若为奇数层将node.val添加至tmp尾部否则添加至tmp头部添加子节点若node的左右子节点不为空则加入deque将当前层结果tmp转化为 list 并添加入res返回值返回打印结果列表res。三种语言实现class Solution: def decorateRecord(self, root: TreeNode) - List[List[int]]: if not root: return [] res, deque [], collections.deque([root]) while deque: tmp collections.deque() for _ in range(len(deque)): node deque.popleft() if len(res) % 2 0: tmp.append(node.val) # 奇数层 - 插入队列尾部 else: tmp.appendleft(node.val) # 偶数层 - 插入队列头部 if node.left: deque.append(node.left) if node.right: deque.append(node.right) res.append(list(tmp)) return resclass Solution { public ListListInteger decorateRecord(TreeNode root) { QueueTreeNode queue new LinkedList(); ListListInteger res new ArrayList(); if(root ! null) queue.add(root); while(!queue.isEmpty()) { LinkedListInteger tmp new LinkedList(); for(int i queue.size(); i 0; i--) { TreeNode node queue.poll(); if(res.size() % 2 0) tmp.addLast(node.val); else tmp.addFirst(node.val); if(node.left ! null) queue.add(node.left); if(node.right ! null) queue.add(node.right); } res.add(tmp); } return res; } }class Solution { public: vectorvectorint decorateRecord(TreeNode* root) { dequeTreeNode* deque; vectorvectorint res; if(root ! NULL) deque.push_back(root); while(!deque.empty()) { dequeint tmp; // 注意此处示意为存储 int 的双端队列 ... } } };说明方法一在 Python 与 Java 中可直接用双端队列tmp承接结果C 实现若使用std::dequeint承接层内结果同样能在队头/队尾以 $O(1)$ 复杂度插入。语言要点Python使用collections中的双端队列deque()其popleft()方法可达到 $O(1)$ 时间复杂度而列表 list 的pop(0)方法时间复杂度为 $O(N)$因此本题必须用双端队列做 BFS 队列。Java将链表LinkedList作为双端队列使用addFirst/addLast均为 $O(1)$。复杂度分析时间复杂度 $O(N)$$N$ 为二叉树的节点数量BFS 需循环 $N$ 次占用 $O(N)$双端队列的队首和队尾的添加和删除操作的时间复杂度均为 $O(1)$。空间复杂度 $O(N)$最差情况下即当树为满二叉树时最多有 $N/2$ 个树节点同时在deque中使用 $O(N)$ 大小的额外空间。方法二层序遍历 双端队列奇偶层逻辑分离核心思路与改进点方法一代码简短、容易实现但需要判断每个节点的所在层奇偶性即冗余了 $N$ 次判断。通过将奇偶层逻辑拆分可以消除冗余的判断——奇数层和偶数层各自拥有独立的出队方向与入队方向两个循环交替执行。算法流程与方法一对比仅 BFS 循环不同。BFS 循环循环打印奇 / 偶数层当deque为空时跳出打印奇数层从左向右打印先左后右加入下层节点若deque为空说明向下无偶数层则跳出打印偶数层从右向左打印先右后左加入下层节点。这里的精髓在于偶数层从deque的尾部出队pop()同时把子节点按先右后左的顺序appendleft到队头。这样出队的顺序天然是右→左且入队的子节点顺序恰好保证下一轮奇数层从左向右读取时仍然是先左后右。代码class Solution: def decorateRecord(self, root: TreeNode) - List[List[int]]: if not root: return [] res, deque [], collections.deque() deque.append(root) while deque: tmp [] # 打印奇数层 for _ in range(len(deque)): # 从左向右打印 node deque.popleft() tmp.append(node.val) # 先左后右加入下层节点 if node.left: deque.append(node.left) if node.right: deque.append(node.right) res.append(tmp) if not deque: break # 若为空则提前跳出 # 打印偶数层 tmp [] for _ in range(len(deque)): # 从右向左打印 node deque.pop() tmp.append(node.val) # 先右后左加入下层节点 if node.right: deque.appendleft(node.right) if node.left: deque.appendleft(node.left) res.append(tmp) return resclass Solution { public ListListInteger decorateRecord(TreeNode root) { DequeTreeNode deque new LinkedList(); ListListInteger res new ArrayList(); if(root ! null) deque.add(root); while(!deque.isEmpty()) { // 打印奇数层 ListInteger tmp new ArrayList(); for(int i deque.size(); i 0; i--) { // 从左向右打印 TreeNode node deque.removeFirst(); tmp.add(node.val); // 先左后右加入下层节点 if(node.left ! null) deque.addLast(node.left); if(node.right ! null) deque.addLast(node.right); } res.add(tmp); if(deque.isEmpty()) break; // 若为空则提前跳出 // 打印偶数层 tmp new ArrayList(); for(int i deque.size(); i 0; i--) { // 从右向左打印 TreeNode node deque.removeLast(); tmp.add(node.val); // 先右后左加入下层节点 if(node.right ! null) deque.addFirst(node.right); if(node.left ! null) deque.addFirst(node.left); } res.add(tmp); } return res; } }class Solution { public: vectorvectorint decorateRecord(TreeNode* root) { dequeTreeNode* deque; vectorvectorint res; if(root ! NULL) deque.push_back(root); while(!deque.empty()) { // 打印奇数层 vectorint tmp; for(int i deque.size(); i 0; i--) { // 从左向右打印 TreeNode* node deque.front(); deque.pop_front(); tmp.push_back(node-val); // 先左后右加入下层节点 if(node-left ! NULL) deque.push_back(node-left); if(node-right ! NULL) deque.push_back(node-right); } res.push_back(tmp); if(deque.empty()) break; // 若为空则提前跳出 // 打印偶数层 tmp.clear(); for(int i deque.size(); i 0; i--) { // 从右向左打印 TreeNode* node deque.back(); deque.pop_back(); tmp.push_back(node-val); // 先右后左加入下层节点 if(node-right ! NULL) deque.push_front(node-right); if(node-left ! NULL) deque.push_front(node-left); } res.push_back(tmp); } return res; } };复杂度分析时间复杂度 $O(N)$同方法一但省去了每层节点逐一判断奇偶性的 $N$ 次分支判断常数因子更小。空间复杂度 $O(N)$同方法一。方法三层序遍历 倒序核心思路此方法的优点是只用普通列表即可无需双端队列等额外数据结构。偶数层倒序若res的长度为奇数说明当前是偶数层则对tmp执行倒序操作。也就是说先完全按标准层序遍历从左到右收集当前层节点输出前判断如果当前是偶数层res.size() % 2 1就把这一层的列表整体翻转。代码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[::-1] if len(res) % 2 else tmp) return resclass 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); } if(res.size() % 2 1) Collections.reverse(tmp); res.add(tmp); } return res; } }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--) { TreeNode* node que.front(); que.pop(); tmp.push_back(node-val); if(node-left ! NULL) que.push(node-left); if(node-right ! NULL) que.push(node-right); } if(res.size() % 2 1) reverse(tmp.begin(), tmp.end()); res.push_back(tmp); } return res; } };复杂度分析时间复杂度 $O(N)$$N$ 为二叉树的节点数量BFS 需循环 $N$ 次占用 $O(N)$共完成少于 $N$ 个节点的倒序操作占用 $O(N)$。空间复杂度 $O(N)$最差情况下即当树为满二叉树时最多有 $N/2$ 个树节点同时在queue中使用 $O(N)$ 大小的额外空间。三方法对比与选型建议对比维度方法一双端队列统一判断方法二奇偶层逻辑分离方法三层序遍历 倒序核心数据结构双端队列deque做 BFS层内结果也用双端队列双端队列deque两端交替出队/入队普通队列queue即可奇偶判断次数每个节点判断一次$N$ 次无需逐节点判断逻辑拆分到两个循环每层判断一次层数次代码简洁度代码最短最容易实现逻辑最清晰代码较长代码最短且最直观额外操作无无偶数层整体倒序$O(N)$ 总量时间复杂度$O(N)$$O(N)$常数因子更小$O(N)$空间复杂度$O(N)$$O(N)$$O(N)$选型建议面试快速作答、追求代码最短 → 方法一或方法三追求常数级性能最优、逻辑自解释 → 方法二若环境不支持双端队列如某些简化实现 → 方法三最稳妥。仓库源码印证与本地运行验证LeetCode-Book 仓库完整收录了本题的三种解法源码均位于 sword_for_offer/codes/python/ 目录下与文档一一对应sfo_32iii_print_a_binary_tree_topbottom_iii_s1.py对应方法一层序遍历 双端队列统一判断sfo_32iii_print_a_binary_tree_topbottom_iii_s2.py对应方法二奇偶层逻辑分离sfo_32iii_print_a_binary_tree_topbottom_iii_s3.py对应方法三层序遍历 倒序。这三份源码与文档中的 Python 解法代码完全一致仓库版本将方法名写作levelOrder并内置了完整的测试驱动代码可在本地直接运行验证。仓库测试脚手架以 sfo_32iii_print_a_binary_tree_topbottom_iii_s1.py 为例其结构为from include import * # Solution Code class Solution: def levelOrder(self, root: TreeNode) - 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)其中两个关键工具来自仓库的 include 工具包list_to_tree(arr)定义在 binary_tree.py按层序遍历序列None表示空节点构建二叉树内部同样用collections.deque做 BFS 建树print_matrix(mat)定义在 print_util.py将二维结果按矩阵形式格式化打印。测试用例使用[3, 9, 20, None, None, 15, 7]这棵标准满二叉树根 3左 9、右 2020 的左 15、右 7预期输出为锯齿形结果[[3], [20, 9], [15, 7]]。在仓库的sword_for_offer/codes/python/目录下直接执行python sfo_32iii_print_a_binary_tree_topbottom_iii_s1.py python sfo_32iii_print_a_binary_tree_topbottom_iii_s2.py python sfo_32iii_print_a_binary_tree_topbottom_iii_s3.py三个脚本将分别输出一致的锯齿形层序结果可直观验证三种解法正确性。跨语言一致性与 Python 源码对应仓库在 sword_for_offer/codes/java/sfo_32iii_print_a_binary_tree_topbottom_iii_s1/ 与 sword_for_offer/codes/cpp/sfo_32iii_print_a_binary_tree_topbottom_iii_s1/ 等目录中收录了同题的 Java / C 实现解题思路与本文三方法一一对应适合对照学习多语言写法。此外本题的经典版本还收录于《Krahets 笔面试精选 88 题》的 lc_103 锯齿形层序遍历三版源码对应 文档说明锯齿形遍历是 BFS 家族的常考变形值得反复练习。总结LCR 151「彩灯装饰记录 III」考查的是 BFS 层序遍历的变形能力。三种解法共享同一套 BFS 框架——队列维护待访问节点 按层快照长度切分层次差别仅在偶数层的反向输出手段双端队列头插方法一、双端队列双向出队 反向入队方法二、普通列表输出后整体倒序方法三。三者时间复杂度均为 $O(N)$空间复杂度均为 $O(N)$实践中应优先选择自己最易写对、最易讲清的版本同时理解其余解法的思路以应对面试官关于能否不用双端队列能否去掉逐节点奇偶判断的追问。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考