LeetCode-Go 题解107. Binary Tree Level Order Traversal II 自底向上层序遍历【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文深入讲解 LeetCode 第 107 题「二叉树的层序遍历 II」给定一棵二叉树按「自底向上」的顺序返回各层节点值。文章以本仓库leetcode/0107.Binary-Tree-Level-Order-Traversal-II目录下的完整 Go 实现为主线从 BFS 队列层序遍历的底层机制、curNum/nextLevelNum双计数器的工作原理到自底向上的结果翻转再到配套测试用例与structures树工具函数的使用带你彻底掌握这道经典二叉树题目的工程化解法并能在仓库中直接运行验证。题目理解与示例分析题目描述给定一棵二叉树返回其节点值的自底向上的层序遍历bottom-up level order traversal。要求从叶子层到根节点、每一层内从左到右依次收集节点值。以题目给出的二叉树[3, 9, 20, null, null, 15, 7]为例其树形结构如下3 / \ 9 20 / \ 15 7自顶向下的层序遍历结果是[ [3], [9, 20], [15, 7] ]而本题要求从下到上输出因此最终结果为[ [15, 7], [9, 20], [3] ]注意两点关键约束一是层与层之间的顺序完全反转但每一层内部的左右顺序保持不变如[15, 7]而非[7, 15]二是空树的合法输出是空切片[]单节点树输出[[1]]这两个边界在测试用例中都有覆盖。与 102 题的关系自底向上层序遍历可以看作是 102 题「Binary Tree Level Order Traversal」的变体先按常规方式得到自顶向下的层序结果再对整组结果做一次整体反转即可。仓库中本题的实现正是采用了这一先正向、后翻转的简洁策略。解题思路单队列 BFS 结果反转为什么选择队列层序遍历天然适合 BFS广度优先搜索使用一个先进先出的队列从根节点开始每访问一个节点就把它的左右孩子依次入队即可保证逐层、层内从左到右的访问顺序。原文档指出用一个队列即可实现仓库源码也正是如此且没有引入任何额外的数据结构辅助分层而是用两个计数器完成层的切分。整体实现结构本题实现由两个函数协作完成源码见 107. Binary Tree Level Order Traversal II.golevelOrder(root *TreeNode) [][]int完成自顶向下的 BFS 层序遍历返回按层分组的节点值levelOrderBottom(root *TreeNode) [][]int调用levelOrder拿到正向结果后从尾部到头部逐层追加到新切片得到自底向上结果。反转部分的实现细节func levelOrderBottom(root *TreeNode) [][]int { tmp : levelOrder(root) res : [][]int{} for i : len(tmp) - 1; i 0; i-- { res append(res, tmp[i]) } return res }这里采用新建结果切片、倒序追加的方式而不是原地交换每一层tmp[i]是独立的[]int切片倒序追加不会破坏各层内部顺序对于空树levelOrder返回[][]int{}循环不会执行函数直接返回空切片与预期一致。源码级原理剖析BFS 双计数器分层levelOrder是整个算法的核心它只用一个队列和两个计数器就完成了完整的分层func levelOrder(root *TreeNode) [][]int { if root nil { return [][]int{} } queue : []*TreeNode{} queue append(queue, root) curNum, nextLevelNum, res, tmp : 1, 0, [][]int{}, []int{} 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 { res append(res, tmp) curNum nextLevelNum nextLevelNum 0 tmp []int{} } } return res }三个变量的职责变量初始值职责queue[root]保存待访问的节点同时承载下一层节点的暂存curNum1当前层剩余待出队节点数用于界定当前层的边界nextLevelNum0下一层累计入队的节点数当前层耗尽时接替curNumtmp[]int{}暂存当前层已收集的节点值逐层推进的完整流程根节点入队curNum 1从队首取出一个节点queue queue[1:]完成出队将其非空左右孩子入队并让nextLevelNum同时把节点值追加进tmpcurNum--当curNum 0时说明当前层已全部处理完把tmp追加进res并将curNum nextLevelNum、nextLevelNum 0、tmp重置为空切片进入下一层当队列为空时所有层均已处理完毕返回res。以示例树为例第一层只有根节点 3出队时 9、20 入队nextLevelNum 2curNum归零后触发换层第二层处理 9、20入队 15、7第三层处理 15、7 后队列为空BFS 结束。整个过程不需要在队列中插入任何层分隔标记仅靠数值计数即可精确切分层次这是该实现最值得学习的点。复杂度分析时间复杂度O(n)每个节点恰好入队、出队各一次附加一次结果整体反转仍为线性空间复杂度O(n)队列最多同时容纳一层的节点最坏情况为满二叉树最后一层的 n/2 个节点加上结果切片res与每层暂存tmp的开销总体为 O(n)。树节点类型与测试数据构造TreeNode 类型定义本题源码开头通过类型别名复用了仓库公共结构体// TreeNode define type TreeNode structures.TreeNode该类型定义在 structures/TreeNode.go结构如下type TreeNode struct { Val int Left *TreeNode Right *TreeNode }仓库将二叉树、链表等通用数据结构抽离到独立的structures包所有 LeetCode 题解统一复用保证了类型一致并避免了每个题目重复定义。用 Ints2TreeNode 构造测试树测试代码通过structures.Ints2TreeNode把 LeetCode 风格的层序数组转换成*TreeNode见 107. Binary Tree Level Order Traversal II_test.gopara107{[]int{3, 9, 20, structures.NULL, structures.NULL, 15, 7}}, ans107{[][]int{{15, 7}, {9, 20}, {3}}},其中structures.NULL定义见 structures/TreeNode.go是一个哨兵值// NULL 方便添加测试数据 var NULL -1 63Ints2TreeNode的转换逻辑structures/TreeNode.go同样基于队列以数组首元素建根逐层为每个节点挂载左右孩子遇到NULL则跳过该子节点。注意它并不支持任意层深的稀疏树仅适用于按层补齐的标准 LeetCode 输入格式这也是在构造复杂测试数据时需要留意的限制。测试用例与运行验证用例设计仓库的测试文件使用参数 期望答案的结构化写法覆盖了三类典型场景输入层序数组期望输出覆盖场景[]空树[]空树边界[1][[1]]单节点树[3, 9, 20, NULL, NULL, 15, 7][[15, 7], [9, 20], [3]]完整的多层二叉树题目示例测试主流程Test_Problem107遍历所有用例将层序数组经Ints2TreeNode建树后调用levelOrderBottom并打印输入与输出用于人工核对。本地运行方式在仓库根目录执行以下命令即可运行本题测试go test -v ./leetcode/0107.Binary-Tree-Level-Order-Traversal-II/ -run Test_Problem107预期会输出形如以下的内容测试通过且无失败断言------------------------Leetcode Problem 107------------------------ 【input】:[] 【output】:[] 【input】:[1] 【output】:[[1]] 【input】:[3 9 20 -9223372036854775808 -9223372036854775808 15 7] 【output】:[[15 7] [9 20] [3]]-9223372036854775808正是structures.NULL-1 63的实际取值说明哨兵值在测试输出中以极值形式呈现不影响断言正确性。该测试属于仓库「100% test coverage」工程实践的一部分仓库根目录的 gotest.sh 与 coverage.txt 记录了全量覆盖率运行方式与结果。小结本题通过队列 BFS 双计数器分层 结果整体反转三步即可优雅解决curNum与nextLevelNum的组合避免了在队列中混入分隔符或记录每层节点数数组是层序遍历中值得反复揣摩的经典写法而把自底向上的需求转化为一次线性反转则体现了先解决正向问题、再变换输出的通用解题思路。仓库中本题的实现与测试实现、测试可直接作为模板迁移到 102 题正向层序及各类锯齿形层序变体题中。【免费下载链接】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 题解107. Binary Tree Level Order Traversal II 自底向上层序遍历【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文深入讲解 LeetCode 第 107 题「二叉树的层序遍历 II」给定一棵二叉树按「自底向上」的顺序返回各层节点值。文章以本仓库leetcode/0107.Binary-Tree-Level-Order-Traversal-II目录下的完整 Go 实现为主线从 BFS 队列层序遍历的底层机制、curNum/nextLevelNum双计数器的工作原理到自底向上的结果翻转再到配套测试用例与structures树工具函数的使用带你彻底掌握这道经典二叉树题目的工程化解法并能在仓库中直接运行验证。题目理解与示例分析题目描述给定一棵二叉树返回其节点值的自底向上的层序遍历bottom-up level order traversal。要求从叶子层到根节点、每一层内从左到右依次收集节点值。以题目给出的二叉树[3, 9, 20, null, null, 15, 7]为例其树形结构如下3 / \ 9 20 / \ 15 7自顶向下的层序遍历结果是[ [3], [9, 20], [15, 7] ]而本题要求从下到上输出因此最终结果为[ [15, 7], [9, 20], [3] ]注意两点关键约束一是层与层之间的顺序完全反转但每一层内部的左右顺序保持不变如[15, 7]而非[7, 15]二是空树的合法输出是空切片[]单节点树输出[[1]]这两个边界在测试用例中都有覆盖。与 102 题的关系自底向上层序遍历可以看作是 102 题「Binary Tree Level Order Traversal」的变体先按常规方式得到自顶向下的层序结果再对整组结果做一次整体反转即可。仓库中本题的实现正是采用了这一先正向、后翻转的简洁策略。解题思路单队列 BFS 结果反转为什么选择队列层序遍历天然适合 BFS广度优先搜索使用一个先进先出的队列从根节点开始每访问一个节点就把它的左右孩子依次入队即可保证逐层、层内从左到右的访问顺序。原文档指出用一个队列即可实现仓库源码也正是如此且没有引入任何额外的数据结构辅助分层而是用两个计数器完成层的切分。整体实现结构本题实现由两个函数协作完成源码见 107. Binary Tree Level Order Traversal II.golevelOrder(root *TreeNode) [][]int完成自顶向下的 BFS 层序遍历返回按层分组的节点值levelOrderBottom(root *TreeNode) [][]int调用levelOrder拿到正向结果后从尾部到头部逐层追加到新切片得到自底向上结果。反转部分的实现细节func levelOrderBottom(root *TreeNode) [][]int { tmp : levelOrder(root) res : [][]int{} for i : len(tmp) - 1; i 0; i-- { res append(res, tmp[i]) } return res }这里采用新建结果切片、倒序追加的方式而不是原地交换每一层tmp[i]是独立的[]int切片倒序追加不会破坏各层内部顺序对于空树levelOrder返回[][]int{}循环不会执行函数直接返回空切片与预期一致。源码级原理剖析BFS 双计数器分层levelOrder是整个算法的核心它只用一个队列和两个计数器就完成了完整的分层func levelOrder(root *TreeNode) [][]int { if root nil { return [][]int{} } queue : []*TreeNode{} queue append(queue, root) curNum, nextLevelNum, res, tmp : 1, 0, [][]int{}, []int{} 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 { res append(res, tmp) curNum nextLevelNum nextLevelNum 0 tmp []int{} } } return res }三个变量的职责变量初始值职责queue[root]保存待访问的节点同时承载下一层节点的暂存curNum1当前层剩余待出队节点数用于界定当前层的边界nextLevelNum0下一层累计入队的节点数当前层耗尽时接替curNumtmp[]int{}暂存当前层已收集的节点值逐层推进的完整流程根节点入队curNum 1从队首取出一个节点queue queue[1:]完成出队将其非空左右孩子入队并让nextLevelNum同时把节点值追加进tmpcurNum--当curNum 0时说明当前层已全部处理完把tmp追加进res并将curNum nextLevelNum、nextLevelNum 0、tmp重置为空切片进入下一层当队列为空时所有层均已处理完毕返回res。以示例树为例第一层只有根节点 3出队时 9、20 入队nextLevelNum 2curNum归零后触发换层第二层处理 9、20入队 15、7第三层处理 15、7 后队列为空BFS 结束。整个过程不需要在队列中插入任何层分隔标记仅靠数值计数即可精确切分层次这是该实现最值得学习的点。复杂度分析时间复杂度O(n)每个节点恰好入队、出队各一次附加一次结果整体反转仍为线性空间复杂度O(n)队列最多同时容纳一层的节点最坏情况为满二叉树最后一层的 n/2 个节点加上结果切片res与每层暂存tmp的开销总体为 O(n)。树节点类型与测试数据构造TreeNode 类型定义本题源码开头通过类型别名复用了仓库公共结构体// TreeNode define type TreeNode structures.TreeNode该类型定义在 structures/TreeNode.go结构如下type TreeNode struct { Val int Left *TreeNode Right *TreeNode }仓库将二叉树、链表等通用数据结构抽离到独立的structures包所有 LeetCode 题解统一复用保证了类型一致并避免了每个题目重复定义。用 Ints2TreeNode 构造测试树测试代码通过structures.Ints2TreeNode把 LeetCode 风格的层序数组转换成*TreeNode见 107. Binary Tree Level Order Traversal II_test.gopara107{[]int{3, 9, 20, structures.NULL, structures.NULL, 15, 7}}, ans107{[][]int{{15, 7}, {9, 20}, {3}}},其中structures.NULL定义见 structures/TreeNode.go是一个哨兵值// NULL 方便添加测试数据 var NULL -1 63Ints2TreeNode的转换逻辑structures/TreeNode.go同样基于队列以数组首元素建根逐层为每个节点挂载左右孩子遇到NULL则跳过该子节点。注意它并不支持任意层深的稀疏树仅适用于按层补齐的标准 LeetCode 输入格式这也是在构造复杂测试数据时需要留意的限制。测试用例与运行验证用例设计仓库的测试文件使用参数 期望答案的结构化写法覆盖了三类典型场景输入层序数组期望输出覆盖场景[]空树[]空树边界[1][[1]]单节点树[3, 9, 20, NULL, NULL, 15, 7][[15, 7], [9, 20], [3]]完整的多层二叉树题目示例测试主流程Test_Problem107遍历所有用例将层序数组经Ints2TreeNode建树后调用levelOrderBottom并打印输入与输出用于人工核对。本地运行方式在仓库根目录执行以下命令即可运行本题测试go test -v ./leetcode/0107.Binary-Tree-Level-Order-Traversal-II/ -run Test_Problem107预期会输出形如以下的内容测试通过且无失败断言------------------------Leetcode Problem 107------------------------ 【input】:[] 【output】:[] 【input】:[1] 【output】:[[1]] 【input】:[3 9 20 -9223372036854775808 -9223372036854775808 15 7] 【output】:[[15 7] [9 20] [3]]-9223372036854775808正是structures.NULL-1 63的实际取值说明哨兵值在测试输出中以极值形式呈现不影响断言正确性。该测试属于仓库「100% test coverage」工程实践的一部分仓库根目录的 gotest.sh 与 coverage.txt 记录了全量覆盖率运行方式与结果。小结本题通过队列 BFS 双计数器分层 结果整体反转三步即可优雅解决curNum与nextLevelNum的组合避免了在队列中混入分隔符或记录每层节点数数组是层序遍历中值得反复揣摩的经典写法而把自底向上的需求转化为一次线性反转则体现了先解决正向问题、再变换输出的通用解题思路。仓库中本题的实现与测试实现、测试可直接作为模板迁移到 102 题正向层序及各类锯齿形层序变体题中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
