示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文围绕 LeetCode 第 103 题「二叉树的锯齿形层序遍历Binary Tree Zigzag Level Order Traversal」展开系统讲解如何在经典层序遍历BFS的骨架上引入方向标志位实现先从左到右、再从右到左、逐层交替的锯齿形输出。文章完整呈现题目约束、解题思路与复杂度分析并给出 Python、Java、C、Go、TypeScript、Rust、JavaScript 7 种语言的可直接运行的仓库源码级实现。读完本文你将掌握 BFS 层序遍历的通用模板并能用最小改动将其扩展为锯齿形、自底向上等多种层序变体。一、问题描述给定一棵二叉树的根节点root返回其节点值的锯齿形层序遍历。所谓锯齿形是指遍历方向逐层交替第一层从左到右第二层从右到左第三层再从左到右依此类推。对应的中英双语题目文档位于仓库的 README_EN.md 与 README.md。示例 1输入二叉树的结构如下输入root [3,9,20,null,null,15,7] 输出[[3],[20,9],[15,7]]过程拆解第 1 层从左到右访问[3]第 2 层从右到左访问[20, 9]第 3 层从左到右访问[15, 7]。示例 2输入root [1] 输出[[1]]示例 3输入root [] 输出[]数据约束树中节点数目在范围[0, 2000]内-100 Node.val 100。约束条件直接决定了算法选型节点数上限仅 2000即便对每一层做一次整体反转总复杂度依然只有 $O(n)$完全在可接受范围内因此层序收集 按需反转这一朴素策略是最简单且充分的做法。二、解题思路在层序遍历上叠加方向标志2.1 从普通层序遍历出发锯齿形层序遍历与 LeetCode 102「二叉树的层序遍历」见 0102.Binary Tree Level Order Traversal共享同一套 BFS 骨架用队列q保存当前层的节点每一轮循环先记录len(q)固定本轮要处理的节点数量弹出该层的全部节点将其val收集到临时列表t中同时把每个节点的非空左右孩子按顺序入队将t写入结果数组ans进入下一层。这套骨架保证了队列中同一时刻只保存当前层 下一层的节点天然按层推进。2.2 核心改动方向标志位left普通层序每一层都从左到右输出而锯齿形要求逐层反向。为此只需在 BFS 骨架上增加一个方向标志left当left为真true/1时当前层节点值从左到右存入结果数组ans当left为假false/0时当前层节点值从右到左存入结果数组ans。实现上的等价做法是先把本层节点按统一顺序收集进临时列表t当left为假时对t做一次整体反转t[::-1]、Collections.reverse(t)、reverse(t.begin(), t.end())、t.reverse()等再追加到ans。每处理完一层后翻转标志left !left或left ^ 1从而实现方向交替。2.3 为什么孩子仍按从左到右入队一个容易困惑的点是既然本层要从右到左输出是否入队时也要调整孩子顺序不需要也绝不应该。反转只作用于当前层输出顺序这一结果层面而 BFS 队列的职责是确定下一层的访问顺序。孩子始终按左孩子、右孩子顺序入队能保证每一层在队列中的相对顺序始终稳定——无论上一层输出方向如何下一层进入循环时面对的都是一份顺序一致的节点列表。锯齿形的方向变化仅通过输出时的反转体现入队逻辑自始至终不变。这正是 Solution.py 中node.left/node.right无条件顺序入队的原因。2.4 边界情况处理空树root为null/None直接返回空数组[]不做任何入队操作单节点树只有一层方向标志初始为左到右输出[[1]]斜树每个节点只有一个孩子每层只有一个节点反转与否结果相同算法依然正确宽树队列最大宽度即为某一层的节点数最坏情况下接近 $n$这也是空间复杂度的来源。三、复杂度分析设二叉树的节点数为 $n$时间复杂度 $O(n)$每个节点恰好入队、出队一次每一层收集节点值为 $O(\text{层宽})$若需反转该层也为 $O(\text{层宽})$所有层累加后仍为 $O(n)$空间复杂度 $O(n)$队列中最多同时保存一层的节点最坏情况下为整棵树的宽度结果数组ans本身存储全部节点值也需 $O(n)$ 空间。由于题目约束 $n \le 2000$上述 $O(n)$ 方案在时间和空间上都有充足的余量。四、多语言实现详解以下 7 份实现与仓库中的 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js 一一对应可直接复制运行。Python3# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) - List[List[int]]: ans [] if root is None: return ans q deque([root]) ans [] left 1 while q: t [] for _ in range(len(q)): node q.popleft() t.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) ans.append(t if left else t[::-1]) left ^ 1 return ans要点collections.deque提供 $O(1)$ 的popleft()left直接用整数1/0配合异或left ^ 1翻转比布尔值更简洁t[::-1]是列表切片的反转写法。Java/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger ans new ArrayList(); if (root null) { return ans; } DequeTreeNode q new ArrayDeque(); q.offer(root); boolean left true; while (!q.isEmpty()) { ListInteger t new ArrayList(); for (int n q.size(); n 0; --n) { TreeNode node q.poll(); t.add(node.val); if (node.left ! null) { q.offer(node.left); } if (node.right ! null) { q.offer(node.right); } } if (!left) { Collections.reverse(t); } ans.add(t); left !left; } return ans; } }要点ArrayDeque作为队列offer/poll配对使用关键技巧是在for循环初始化处用int n q.size()固定本层待处理数量避免循环过程中入队导致队列长度变化。C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorvectorint zigzagLevelOrder(TreeNode* root) { vectorvectorint ans; if (!root) { return ans; } queueTreeNode* q{{root}}; int left 1; while (!q.empty()) { vectorint t; for (int n q.size(); n; --n) { auto node q.front(); q.pop(); t.emplace_back(node-val); if (node-left) { q.push(node-left); } if (node-right) { q.push(node-right); } } if (!left) { reverse(t.begin(), t.end()); } ans.emplace_back(t); left ^ 1; } return ans; } };要点std::queue配合front()pop()出队emplace_back就地构造避免拷贝反转使用algorithm的std::reverseleft同样以整数配合异或翻转。Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func zigzagLevelOrder(root *TreeNode) (ans [][]int) { if root nil { return } q : []*TreeNode{root} left : true for len(q) 0 { t : []int{} for n : len(q); n 0; n-- { node : q[0] q q[1:] t append(t, node.Val) if node.Left ! nil { q append(q, node.Left) } if node.Right ! nil { q append(q, node.Right) } } if !left { for i, j : 0, len(t)-1; i j; i, j i1, j-1 { t[i], t[j] t[j], t[i] } } ans append(ans, t) left !left } return }要点Go 用切片模拟队列出队采用node : q[0]; q q[1:]的手动切片操作反转不依赖标准库直接用双指针i/j原地交换利用命名返回值(ans [][]int)直接return。TypeScript/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } * } */ function zigzagLevelOrder(root: TreeNode | null): number[][] { const ans: number[][] []; if (!root) { return ans; } const q: TreeNode[] [root]; let left: number 1; while (q.length) { const t: number[] []; const qq: TreeNode[] []; for (const { val, left, right } of q) { t.push(val); left qq.push(left); right qq.push(right); } ans.push(left ? t : t.reverse()); q.splice(0, q.length, ...qq); left ^ 1; } return ans; }要点这里没有用索引式for循环而是解构当前层节点{ val, left, right }遍历下一层节点收集到新数组qq循环结束后用q.splice(0, q.length, ...qq)一次性替换队列内容思路与双数组逐层滚动一致避免了队首弹出操作。Rust// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) - Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::cell::RefCell; use std::collections::VecDeque; use std::rc::Rc; impl Solution { pub fn zigzag_level_order(root: OptionRcRefCellTreeNode) - VecVeci32 { let mut ans Vec::new(); let mut left true; if let Some(root_node) root { let mut q VecDeque::new(); q.push_back(root_node); while !q.is_empty() { let mut t Vec::new(); for _ in 0..q.len() { if let Some(node) q.pop_front() { let node_ref node.borrow(); t.push(node_ref.val); if let Some(ref left) node_ref.left { q.push_back(Rc::clone(left)); } if let Some(ref right) node_ref.right { q.push_back(Rc::clone(right)); } } } if !left { t.reverse(); } ans.push(t); left !left; } } ans } }要点Rust 的TreeNode用RcRefCellTreeNode表达共享所有权读取节点需node.borrow()VecDeque的pop_front()提供 $O(1)$ 出队把孩子压入队列时必须Rc::clone以共享同一棵树的所有权而不发生移动。JavaScript/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val (valundefined ? 0 : val) * this.left (leftundefined ? null : left) * this.right (rightundefined ? null : right) * } */ /** * param {TreeNode} root * return {number[][]} */ var zigzagLevelOrder function (root) { const ans []; if (!root) { return ans; } const q [root]; let left 1; while (q.length) { const t []; const qq []; for (const { val, left, right } of q) { t.push(val); left qq.push(left); right qq.push(right); } ans.push(left ? t : t.reverse()); q.splice(0, q.length, ...qq); left ^ 1; } return ans; };要点与 TypeScript 版本同构——利用解构与短路把非空孩子收集到qq再整体替换qt.reverse()为原地反转。五、仓库源码对照与验证上述 7 份实现均可在仓库中直接找到独立源码文件彼此完全一致可作为本地运行与断点调试的参考语言仓库文件路径Python3Solution.pyJavaSolution.javaCSolution.cppGoSolution.goTypeScriptSolution.tsRustSolution.rsJavaScriptSolution.js以 Solution.py 为例将三个示例分别作为输入可以验证root [3,9,20,null,null,15,7]→[[3],[20,9],[15,7]]root [1]→[[1]]root []→[]。同时本仓库 solution/0100-0199 目录还收录了 LeetCode 102「二叉树的层序遍历」等其他层序变体题目可以作为横向对比练习102 不反转任何一层103 逐层交替反转两者仅在标志位处理上有差异。六、进阶讨论反转法与等价变体6.1 为什么收集后反转是优解从数据结构角度反转一层的代价与其长度成正比所有层累加为 $O(n)$与 BFS 本身同量级因此不会引入额外复杂度开销。相比入队时按方向插入的方案反转法逻辑更直白、不易出错是面试与工程实现中的首选。6.2 可选的等价变体思路层面从算法角度可以推断至少还有两种等价实现路径复杂度与反转法相同双端队列头插法仍按统一顺序入队但写入结果时对右到左的层改用deque的头部插入appendleft省去反转这一步代价是头插在部分数据结构上是 $O(1)$如 Pythondeque但在数组上可能退化为 $O(\text{层宽})$实际收益有限DFS 按层累计用深度优先遍历按depth分组偶数深度层从 0 计正序、奇数深度层逆序同样能得到锯齿形结果但需要额外的结果数组定位逻辑。无论选择哪种变体核心思想一致层序遍历负责分层方向标志负责整序两者解耦。理解了这一点再遇到按层蛇形输出矩阵二叉树的镜像层序等同类问题都可以直接套用这一思路。6.3 一句话总结在 BFS 层序模板上增加一个逐层翻转的方向标志left配合整层收集 按需反转即可在 $O(n)$ 时间、$O(n)$ 空间内优雅地完成二叉树的锯齿形层序遍历——这正是 README_EN.md 中方法一BFS所给出的标准解。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐FanControl 3 步配好风扇曲线FanControl 3 步配好风扇曲线 打游戏半小时后 CPU 风扇开始高频尖啸白天不干活时机箱风扇却呼呼空转——用台式机的人大概率都碰上过。FanCont桌面应用Open WebUI 部署教程一条命令跑通私有 AI 聊天界面Open WebUI 部署教程一条命令跑通私有 AI 聊天界面 Open WebUI 是开源自托管 AI 聊天平台为 Ollama 与 OpenAI 兼容AI 应用人工智能大模型本地部署RAGAI Agent交互助手前端后端LeetCode 0103 二叉树的锯齿形层序遍历基于 BFS 与双端队列的逐层方向交替算法AlgoNote 题解精讲LeetCode 0103 二叉树的锯齿形层序遍历基于 BFS 与双端队列的逐层方向交替算法AlgoNote 题解精讲 导读 本文围绕「 二叉树的锯齿形教程教育上一篇NFD云解析实战指南深度解析网盘直链解析器扩展架构下一篇如何免费把微信聊天记录导出成HTML面向新手的完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考