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呈现从右到左的顺序，恰好完成锯齿形输出。

算法流程

1. 特例处理：当树的根节点为空，则直接返回空列表[]；
2. 初始化：打印结果空列表res，包含根节点的双端队列deque；
3. BFS 循环：当deque为空时跳出；
   • 新建列表tmp，用于临时存储当前层打印结果；
   • 当前层打印循环：循环次数为当前层节点数（即deque长度）；
     • 出队：队首元素出队，记为node；
     • 打印：若为奇数层，将node.val添加至tmp尾部；否则，添加至tmp头部；
     • 添加子节点：若node的左（右）子节点不为空，则加入deque；
   • 将当前层结果tmp转化为 list 并添加入res；
4. 返回值：返回打印结果列表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 res

class Solution { public List<List<Integer>> decorateRecord(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if(root != null) queue.add(root); while(!queue.isEmpty()) { LinkedList<Integer> 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: vector<vector<int>> decorateRecord(TreeNode* root) { deque<TreeNode*> deque; vector<vector<int>> res; if(root != NULL) deque.push_back(root); while(!deque.empty()) { deque<int> tmp; // 注意：此处示意为存储 int 的双端队列 ... } } };

说明：方法一在 Python 与 Java 中可直接用双端队列tmp承接结果；C++ 实现若使用std::deque<int>承接层内结果，同样能在队头/队尾以 $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为空时跳出；

1. 打印奇数层：从左向右打印，先左后右加入下层节点；
2. 若deque为空，说明向下无偶数层，则跳出；
3. 打印偶数层：从右向左打印，先右后左加入下层节点。

这里的精髓在于：偶数层从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 res

class Solution { public List<List<Integer>> decorateRecord(TreeNode root) { Deque<TreeNode> deque = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); if(root != null) deque.add(root); while(!deque.isEmpty()) { // 打印奇数层 List<Integer> 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: vector<vector<int>> decorateRecord(TreeNode* root) { deque<TreeNode*> deque; vector<vector<int>> res; if(root != NULL) deque.push_back(root); while(!deque.empty()) { // 打印奇数层 vector<int> 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 res

class Solution { public List<List<Integer>> decorateRecord(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); } if(res.size() % 2 == 1) Collections.reverse(tmp); res.add(tmp); } return res; } }

class Solution { public: vector<vector<int>> decorateRecord(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--) { 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)$ 大小的额外空间。

三方法对比与选型建议

选型建议：

• 面试快速作答、追求代码最短 → 方法一或方法三；
• 追求常数级性能最优、逻辑自解释 → 方法二；
• 若环境不支持双端队列（如某些简化实现） → 方法三最稳妥。

仓库源码印证与本地运行验证

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、右 20，20 的左 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