企业官网建设流程全解析

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.go）：

• levelOrder(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 }

三个变量的职责

逐层推进的完整流程

1. 根节点入队，curNum = 1；
2. 从队首取出一个节点（queue = queue[1:]完成出队），将其非空左右孩子入队并让nextLevelNum++，同时把节点值追加进tmp，curNum--；
3. 当curNum == 0时，说明当前层已全部处理完，把tmp追加进res，并将curNum = nextLevelNum、nextLevelNum = 0、tmp重置为空切片，进入下一层；
4. 当队列为空时，所有层均已处理完毕，返回res。

以示例树为例：第一层只有根节点 3，出队时 9、20 入队，nextLevelNum = 2，curNum归零后触发换层；第二层处理 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.go）：

para107{[]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 << 63

Ints2TreeNode的转换逻辑（structures/TreeNode.go）同样基于队列：以数组首元素建根，逐层为每个节点挂载左右孩子，遇到NULL则跳过该子节点。注意它并不支持任意层深的稀疏树，仅适用于"按层补齐"的标准 LeetCode 输入格式，这也是在构造复杂测试数据时需要留意的限制。

测试用例与运行验证

用例设计

仓库的测试文件使用"参数 + 期望答案"的结构化写法，覆盖了三类典型场景：

测试主流程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