LeetCode-Go 103 题详解二叉树锯齿形层序遍历的三种 Go 实现双队列、递归、单队列分层计数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中第 103 题的题解文档与配套源码完整讲解“二叉树锯齿形层序遍历”Binary Tree Zigzag Level Order Traversal的题目要求、示例与解题思路并逐一剖析仓库中提供的三种 Go 解法双队列按层处理、递归 DFS 插入、以及单队列配合当前层计数器的实现。读完本文你将能够复现这三种解法的核心机制理解锯齿形遍历中“层内方向交替”的三种落地方式事后反转、头部插入、倒序写入并掌握仓库测试体系如何验证解法正确性。题目描述与示例原题LeetCode 103的完整题面在 题解文档 中给出Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between).即给定一棵二叉树返回其节点值的锯齿形层序遍历结果——第一层从左到右第二层从右到左再第三层回到从左到右如此逐层交替。文档中的经典示例给定二叉树[3,9,20,null,null,15,7]其树形结构为3 / \ 9 20 / \ 15 7期望返回的锯齿形层序遍历结果[ [3], [20,9], [15,7] ]注意第二层输出为[20,9]而不是[9,20]奇数层从 0 开始的第 1、3……层需要相对常规层序结果反向。题目大意与解题思路仓库 中文题解 README 将题目大意为“按照 Z 字型层序遍历一棵树”与英文文档的 Problem SummaryTraverse a tree in zigzag level order一致。文档给出的核心解题思路有两条按层序从上到下遍历整棵树但每一层的顺序相对上一层是反转的上一层从左往右下一层就从右往左以此类推。用一个队列即可实现。第 102 题Binary Tree Level Order Traversal和第 107 题Binary Tree Level Order Traversal II都是按层序遍历的问题本题是它们的方向变体。102 题的基础层序遍历实现见 leetcode/0102.Binary-Tree-Level-Order-Traversal可以对照理解。把思路落到实现上仓库提供了三种解法对应 leetcode/0103.Binary-Tree-Zigzag-Level-Order-Traversal/103. Binary Tree Zigzag Level Order Traversal.go 中的zigzagLevelOrder、zigzagLevelOrder0、zigzagLevelOrder1三个函数。三者对“层内反向”的处理手段各不相同事后整体反转、DFS 时头部插入、BFS 时倒序写入这也是本文剖析的重点。前置依赖节点定义、NULL 常量与测试树构造三种解法的输入统一是仓库structures包中的*TreeNode。该类型定义在 structures/TreeNode.go// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // NULL 方便添加测试数据 var NULL -1 63这里NULL被取为int的最小值-163用于在序列化数组中占位表示“空节点”。题解源码通过类型别名type TreeNode structures.TreeNode直接复用该类型避免重复定义。测试侧需要把 LeetCode 的层序数组如[3,9,20,null,null,15,7]还原成二叉树仓库用 Ints2TreeNode 完成这一转换它按 BFS 的顺序消费输入数组遇到NULL占位则跳过子节点创建从而得到与 LeetCode 输入约定一致的树结构。测试用例见 103. Binary Tree Zigzag Level Order Traversal_test.go共四组数据覆盖了空树、单节点、文档示例树和一层为单节点的情况输入层序数组NULL 占位期望输出[][][]int{}[1]{{1}}[3,9,20, NULL, NULL, 15, 7]{{3}, {9, 20}, {15, 7}}[1, 2, 3, 4, NULL, NULL, 5]{{1}, {3, 2}, {4, 5}}其中第三组是文档示例的测试版写法注意测试里的期望输出写的是{{3}, {9, 20}, {15, 7}}即与常规层序相同的表示而题目原始示例中第二层写作[20,9]。从源码结构看仓库测试只调用并打印zigzagLevelOrder的结果、对另外两个解法仅做“跑通不 panic”的调用四组用例的核心作用是覆盖空树/单节点/多层树等结构形态。测试命令由仓库根目录的 gotest.sh 统一提供对leetcode下所有题的包做一次性覆盖率采集go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...模块与版本约束见 go.mod模块名为github.com/halfrost/LeetCode-Gogo 1.19并且通过replace指令把github.com/halfrost/LeetCode-Go/structures映射到本地./structures目录。因此解法文件中的import github.com/halfrost/LeetCode-Go/structures实际解析到仓库内的structures包注意英文题解文档中代码块里的导入路径写作leetcode-go/structures与实际源码存在大小写差异以仓库源码为准。解法一单队列 当前层计数器层末整体反转// 解法一 func zigzagLevelOrder(root *TreeNode) [][]int { if root nil { return [][]int{} } queue : []*TreeNode{} queue append(queue, root) curNum, nextLevelNum, res, tmp, curDir : 1, 0, [][]int{}, []int{}, 0 for len(queue) ! 0 { if curNum 0 { node : queue[0] if node.Left ! nil { queue append(queue, node.Left) nextLevelNum } if node.Right ! nil { queue append(queue, node.Right) nextLevelNum } curNum-- tmp append(tmp, node.Val) queue queue[1:] } if curNum 0 { if curDir 1 { for i, j : 0, len(tmp)-1; i j; i, j i1, j-1 { tmp[i], tmp[j] tmp[j], tmp[i] } } res append(res, tmp) curNum nextLevelNum nextLevelNum 0 tmp []int{} if curDir 0 { curDir 1 } else { curDir 0 } } } return res }这是文档中标注 “Solution one” 的写法也是测试实际调用的主解法。它的状态设计有 5 个变量值得逐个拆解queue用 Go 切片模拟 FIFO 队列队头是queue[0]出队用queue queue[1:]。curNum当前层剩余待处理的节点数初始为 1根节点。nextLevelNum处理当前层节点时顺手统计出的下一层节点总数供当前层耗尽时“换层”使用。tmp当前层收集到的节点值按入队顺序即从左到右追加。curDir方向标记。0表示本层正序、1表示本层需要反转。执行流程是“一个外层循环内嵌两层条件”只要curNum 0就持续从队头取节点、把子节点入队并累计nextLevelNum、把值压入tmp一旦curNum 0说明当前层处理完毕此时若curDir 1就对tmp做首尾双指针整体反转然后把tmp追加进结果、完成换层curNum nextLevelNum并翻转curDir。这套写法的巧妙之处在于队列始终按自然顺序左到右扩展锯齿方向只影响“层结果如何呈现”从而把“遍历”和“排布”两个关注点解耦。时间复杂度为 O(n)每个节点入队、出队各一次反转总代价摊到各层也是 O(n)空间复杂度为 O(n)最宽一层队列 结果切片。需要注意的一个实现细节queue queue[1:]每次出队都保留底层数组引用若用于超大规模树可以改用“头部下标”代替切片截断来避免内存不释放。解法二递归 DFS奇数层头部插入// 解法二 递归 func zigzagLevelOrder0(root *TreeNode) [][]int { var res [][]int search(root, 0, res) return res } func search(root *TreeNode, depth int, res *[][]int) { if root nil { return } for len(*res) depth1 { *res append(*res, []int{}) } if depth%2 0 { (*res)[depth] append((*res)[depth], root.Val) } else { (*res)[depth] append([]int{root.Val}, (*res)[depth]...) } search(root.Left, depth1, res) search(root.Right, depth1, res) }文档将其标注为 “Solution two: recursion”。它与解法一的思路差异最大不维护队列直接用 DFS先左后右深度遍历用depth参数代替“层”的概念for len(*res) depth1懒初始化。首次到达某一深度时才向res追加空切片占位因此res的长度天然等于已访问过的最大深度加一。偶数层depth%2 0与解法一相同直接append到层尾奇数层则用append([]int{root.Val}, (*res)[depth]...)把新值插到层头。由于 DFS 是“先访问左子树再访问右子树”同一层内节点被访问的顺序恰好是左到右奇数层每次都插到头部最终呈现为右到左得到锯齿效果。这种“头部插入”用代码表达非常直白但要留意其代价Go 中把元素插到切片头部需要整体拷贝该层已有元素。从源码结构看某个含 k 个节点的层最多会被插入 k 次、每次拷贝至多 k 个元素该层的开销可达 O(k²)对最坏形状的树如满二叉树总体开销可以推断为 O(n²)。它适合理解锯齿遍历的语义而对性能敏感的场景应优先考虑解法一或解法三。解法三双队列 BFS方向层倒序写入// 解法三 BFS func zigzagLevelOrder1(root *TreeNode) [][]int { res : [][]int{} if root nil { return res } q : []*TreeNode{root} size, i, j, lay, tmp, flag : 0, 0, 0, []int{}, []*TreeNode{}, false for len(q) 0 { size len(q) tmp []*TreeNode{} lay make([]int, size) j size - 1 for i 0; i size; i { root q[0] q q[1:] if !flag { lay[i] root.Val } else { lay[j] root.Val j-- } if root.Left ! nil { tmp append(tmp, root.Left) } if root.Right ! nil { tmp append(tmp, root.Right) } } res append(res, lay) flag !flag q tmp } return res }这是文档标注 “Solution three: BFS” 的写法是三种解法里最经典、工程上最易读的一版双层队列q只装当前层节点tmp收集下一层节点。每轮外层循环开头size len(q)内层循环恰好处理size个节点处理完q tmp进入下一层。这是 LeetCode 102 题层序遍历的标准骨架。预分配 倒序写入lay make([]int, size)预分配当前层结果。flag为false正序层时按lay[i] root.Val从左到右填flag为true反序层时用游标j从size-1起从右到左填j--逐步左移。这样在写入阶段就确定了锯齿顺序完全避免了解法一的事后反转。每层结束flag !flag翻转方向。时间复杂度 O(n)空间复杂度 O(n)且没有解法二头部插入的额外拷贝。对比三个解法可以看到仓库刻意展示了“同一道题的层方向控制”的三种等价手段这是它作为学习材料的价值所在解法遍历方式层边界识别方向控制手段zigzagLevelOrder解法一单队列 BFScurNum/nextLevelNum双计数器层收集完毕后双指针整体反转zigzagLevelOrder0解法二递归 DFS深度参数depth 懒初始化奇数层append到层头zigzagLevelOrder1解法三双队列 BFS每轮循环开头取size反序层用游标j倒序写入预分配切片运行与验证方式仓库是只读的验证方式以“查看与运行测试”为主。单题测试文件与被测函数同包package leetcode运行单题测试go test ./leetcode/0103.Binary-Tree-Zigzag-Level-Order-Traversal/ -v测试会打印每组用例的输入输出【input】/【output】并顺带执行解法二、解法三以确认其可跑通。若要按仓库 CI 的方式对整个leetcode目录做覆盖率回归直接执行根目录的 gotest.sh 即可其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...。小结第 103 题是“层序遍历”家族中引入方向交替的变体仓库题解文档给出了题目、示例与“队列 层序 逐层反向”的思路骨架配套源码则提供了反转、头部插入、倒序写入三种实现路径。从源码结构看解法三双队列 倒序写入在可读性与时间复杂度上最为均衡解法一展示了不额外开队列时的计数式换层技巧解法二则以最小代码量诠释了“锯齿 奇数层反向排布”的语义。结合 102 题、107 题的层序遍历实现对照阅读可以完整覆盖二叉树按层遍历的常见考法。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 103 题详解：二叉树锯齿形层序遍历的三种 Go 实现（双队列、递归、单队列分层计数）
LeetCode-Go 103 题详解二叉树锯齿形层序遍历的三种 Go 实现双队列、递归、单队列分层计数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中第 103 题的题解文档与配套源码完整讲解“二叉树锯齿形层序遍历”Binary Tree Zigzag Level Order Traversal的题目要求、示例与解题思路并逐一剖析仓库中提供的三种 Go 解法双队列按层处理、递归 DFS 插入、以及单队列配合当前层计数器的实现。读完本文你将能够复现这三种解法的核心机制理解锯齿形遍历中“层内方向交替”的三种落地方式事后反转、头部插入、倒序写入并掌握仓库测试体系如何验证解法正确性。题目描述与示例原题LeetCode 103的完整题面在 题解文档 中给出Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between).即给定一棵二叉树返回其节点值的锯齿形层序遍历结果——第一层从左到右第二层从右到左再第三层回到从左到右如此逐层交替。文档中的经典示例给定二叉树[3,9,20,null,null,15,7]其树形结构为3 / \ 9 20 / \ 15 7期望返回的锯齿形层序遍历结果[ [3], [20,9], [15,7] ]注意第二层输出为[20,9]而不是[9,20]奇数层从 0 开始的第 1、3……层需要相对常规层序结果反向。题目大意与解题思路仓库 中文题解 README 将题目大意为“按照 Z 字型层序遍历一棵树”与英文文档的 Problem SummaryTraverse a tree in zigzag level order一致。文档给出的核心解题思路有两条按层序从上到下遍历整棵树但每一层的顺序相对上一层是反转的上一层从左往右下一层就从右往左以此类推。用一个队列即可实现。第 102 题Binary Tree Level Order Traversal和第 107 题Binary Tree Level Order Traversal II都是按层序遍历的问题本题是它们的方向变体。102 题的基础层序遍历实现见 leetcode/0102.Binary-Tree-Level-Order-Traversal可以对照理解。把思路落到实现上仓库提供了三种解法对应 leetcode/0103.Binary-Tree-Zigzag-Level-Order-Traversal/103. Binary Tree Zigzag Level Order Traversal.go 中的zigzagLevelOrder、zigzagLevelOrder0、zigzagLevelOrder1三个函数。三者对“层内反向”的处理手段各不相同事后整体反转、DFS 时头部插入、BFS 时倒序写入这也是本文剖析的重点。前置依赖节点定义、NULL 常量与测试树构造三种解法的输入统一是仓库structures包中的*TreeNode。该类型定义在 structures/TreeNode.go// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // NULL 方便添加测试数据 var NULL -1 63这里NULL被取为int的最小值-163用于在序列化数组中占位表示“空节点”。题解源码通过类型别名type TreeNode structures.TreeNode直接复用该类型避免重复定义。测试侧需要把 LeetCode 的层序数组如[3,9,20,null,null,15,7]还原成二叉树仓库用 Ints2TreeNode 完成这一转换它按 BFS 的顺序消费输入数组遇到NULL占位则跳过子节点创建从而得到与 LeetCode 输入约定一致的树结构。测试用例见 103. Binary Tree Zigzag Level Order Traversal_test.go共四组数据覆盖了空树、单节点、文档示例树和一层为单节点的情况输入层序数组NULL 占位期望输出[][][]int{}[1]{{1}}[3,9,20, NULL, NULL, 15, 7]{{3}, {9, 20}, {15, 7}}[1, 2, 3, 4, NULL, NULL, 5]{{1}, {3, 2}, {4, 5}}其中第三组是文档示例的测试版写法注意测试里的期望输出写的是{{3}, {9, 20}, {15, 7}}即与常规层序相同的表示而题目原始示例中第二层写作[20,9]。从源码结构看仓库测试只调用并打印zigzagLevelOrder的结果、对另外两个解法仅做“跑通不 panic”的调用四组用例的核心作用是覆盖空树/单节点/多层树等结构形态。测试命令由仓库根目录的 gotest.sh 统一提供对leetcode下所有题的包做一次性覆盖率采集go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...模块与版本约束见 go.mod模块名为github.com/halfrost/LeetCode-Gogo 1.19并且通过replace指令把github.com/halfrost/LeetCode-Go/structures映射到本地./structures目录。因此解法文件中的import github.com/halfrost/LeetCode-Go/structures实际解析到仓库内的structures包注意英文题解文档中代码块里的导入路径写作leetcode-go/structures与实际源码存在大小写差异以仓库源码为准。解法一单队列 当前层计数器层末整体反转// 解法一 func zigzagLevelOrder(root *TreeNode) [][]int { if root nil { return [][]int{} } queue : []*TreeNode{} queue append(queue, root) curNum, nextLevelNum, res, tmp, curDir : 1, 0, [][]int{}, []int{}, 0 for len(queue) ! 0 { if curNum 0 { node : queue[0] if node.Left ! nil { queue append(queue, node.Left) nextLevelNum } if node.Right ! nil { queue append(queue, node.Right) nextLevelNum } curNum-- tmp append(tmp, node.Val) queue queue[1:] } if curNum 0 { if curDir 1 { for i, j : 0, len(tmp)-1; i j; i, j i1, j-1 { tmp[i], tmp[j] tmp[j], tmp[i] } } res append(res, tmp) curNum nextLevelNum nextLevelNum 0 tmp []int{} if curDir 0 { curDir 1 } else { curDir 0 } } } return res }这是文档中标注 “Solution one” 的写法也是测试实际调用的主解法。它的状态设计有 5 个变量值得逐个拆解queue用 Go 切片模拟 FIFO 队列队头是queue[0]出队用queue queue[1:]。curNum当前层剩余待处理的节点数初始为 1根节点。nextLevelNum处理当前层节点时顺手统计出的下一层节点总数供当前层耗尽时“换层”使用。tmp当前层收集到的节点值按入队顺序即从左到右追加。curDir方向标记。0表示本层正序、1表示本层需要反转。执行流程是“一个外层循环内嵌两层条件”只要curNum 0就持续从队头取节点、把子节点入队并累计nextLevelNum、把值压入tmp一旦curNum 0说明当前层处理完毕此时若curDir 1就对tmp做首尾双指针整体反转然后把tmp追加进结果、完成换层curNum nextLevelNum并翻转curDir。这套写法的巧妙之处在于队列始终按自然顺序左到右扩展锯齿方向只影响“层结果如何呈现”从而把“遍历”和“排布”两个关注点解耦。时间复杂度为 O(n)每个节点入队、出队各一次反转总代价摊到各层也是 O(n)空间复杂度为 O(n)最宽一层队列 结果切片。需要注意的一个实现细节queue queue[1:]每次出队都保留底层数组引用若用于超大规模树可以改用“头部下标”代替切片截断来避免内存不释放。解法二递归 DFS奇数层头部插入// 解法二 递归 func zigzagLevelOrder0(root *TreeNode) [][]int { var res [][]int search(root, 0, res) return res } func search(root *TreeNode, depth int, res *[][]int) { if root nil { return } for len(*res) depth1 { *res append(*res, []int{}) } if depth%2 0 { (*res)[depth] append((*res)[depth], root.Val) } else { (*res)[depth] append([]int{root.Val}, (*res)[depth]...) } search(root.Left, depth1, res) search(root.Right, depth1, res) }文档将其标注为 “Solution two: recursion”。它与解法一的思路差异最大不维护队列直接用 DFS先左后右深度遍历用depth参数代替“层”的概念for len(*res) depth1懒初始化。首次到达某一深度时才向res追加空切片占位因此res的长度天然等于已访问过的最大深度加一。偶数层depth%2 0与解法一相同直接append到层尾奇数层则用append([]int{root.Val}, (*res)[depth]...)把新值插到层头。由于 DFS 是“先访问左子树再访问右子树”同一层内节点被访问的顺序恰好是左到右奇数层每次都插到头部最终呈现为右到左得到锯齿效果。这种“头部插入”用代码表达非常直白但要留意其代价Go 中把元素插到切片头部需要整体拷贝该层已有元素。从源码结构看某个含 k 个节点的层最多会被插入 k 次、每次拷贝至多 k 个元素该层的开销可达 O(k²)对最坏形状的树如满二叉树总体开销可以推断为 O(n²)。它适合理解锯齿遍历的语义而对性能敏感的场景应优先考虑解法一或解法三。解法三双队列 BFS方向层倒序写入// 解法三 BFS func zigzagLevelOrder1(root *TreeNode) [][]int { res : [][]int{} if root nil { return res } q : []*TreeNode{root} size, i, j, lay, tmp, flag : 0, 0, 0, []int{}, []*TreeNode{}, false for len(q) 0 { size len(q) tmp []*TreeNode{} lay make([]int, size) j size - 1 for i 0; i size; i { root q[0] q q[1:] if !flag { lay[i] root.Val } else { lay[j] root.Val j-- } if root.Left ! nil { tmp append(tmp, root.Left) } if root.Right ! nil { tmp append(tmp, root.Right) } } res append(res, lay) flag !flag q tmp } return res }这是文档标注 “Solution three: BFS” 的写法是三种解法里最经典、工程上最易读的一版双层队列q只装当前层节点tmp收集下一层节点。每轮外层循环开头size len(q)内层循环恰好处理size个节点处理完q tmp进入下一层。这是 LeetCode 102 题层序遍历的标准骨架。预分配 倒序写入lay make([]int, size)预分配当前层结果。flag为false正序层时按lay[i] root.Val从左到右填flag为true反序层时用游标j从size-1起从右到左填j--逐步左移。这样在写入阶段就确定了锯齿顺序完全避免了解法一的事后反转。每层结束flag !flag翻转方向。时间复杂度 O(n)空间复杂度 O(n)且没有解法二头部插入的额外拷贝。对比三个解法可以看到仓库刻意展示了“同一道题的层方向控制”的三种等价手段这是它作为学习材料的价值所在解法遍历方式层边界识别方向控制手段zigzagLevelOrder解法一单队列 BFScurNum/nextLevelNum双计数器层收集完毕后双指针整体反转zigzagLevelOrder0解法二递归 DFS深度参数depth 懒初始化奇数层append到层头zigzagLevelOrder1解法三双队列 BFS每轮循环开头取size反序层用游标j倒序写入预分配切片运行与验证方式仓库是只读的验证方式以“查看与运行测试”为主。单题测试文件与被测函数同包package leetcode运行单题测试go test ./leetcode/0103.Binary-Tree-Zigzag-Level-Order-Traversal/ -v测试会打印每组用例的输入输出【input】/【output】并顺带执行解法二、解法三以确认其可跑通。若要按仓库 CI 的方式对整个leetcode目录做覆盖率回归直接执行根目录的 gotest.sh 即可其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...。小结第 103 题是“层序遍历”家族中引入方向交替的变体仓库题解文档给出了题目、示例与“队列 层序 逐层反向”的思路骨架配套源码则提供了反转、头部插入、倒序写入三种实现路径。从源码结构看解法三双队列 倒序写入在可读性与时间复杂度上最为均衡解法一展示了不额外开队列时的计数式换层技巧解法二则以最小代码量诠释了“锯齿 奇数层反向排布”的语义。结合 102 题、107 题的层序遍历实现对照阅读可以完整覆盖二叉树按层遍历的常见考法。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考