企业官网建设流程全解析

LeetCode 102 二叉树层序遍历：LeetCode-Go 中基于队列的 BFS 与 DFS 分层两种解法

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文以 LeetCode-Go 仓库中 102. Binary Tree Level Order Traversal（二叉树层序遍历）的官方题解文档为主线，完整解析题目的输入输出约定、两种解法（队列实现的 BFS、递归实现的 DFS 分层收集）的完整 Go 代码，并结合仓库中的 TreeNode 数据结构、测试用例与 覆盖率脚本 说明如何在本地验证实现。读完后你可以掌握二叉树按层遍历的两种经典实现思路，以及该仓库中题目目录、数据结构包和测试体系的组织方式。

题目描述

给定一棵二叉树，返回其节点值的层序遍历结果，即从左到右、逐层从上到下。

以题目文档 0102.Binary-Tree-Level-Order-Traversal.md 中的示例为例，输入二叉树按层序数组表示为[3,9,20,null,null,15,7]：

3 / \ 9 20 / \ 15 7

期望输出为每一层一个子数组：

[ [3], [9,20], [15,7] ]

题目的核心难点只有一个：如何把"连续出队的节点"按层切分开，让输出中每一层对应一个独立的[]int。

仓库中的题目组织方式

在 LeetCode-Go 仓库中，该题的实体目录为 leetcode/0102.Binary-Tree-Level-Order-Traversal，包含三个文件：

• 解法实现：levelOrder（BFS）与levelOrder1（DFS）两个函数；
• 测试文件：定义question102用例并驱动两个解法运行；
• 中文题解 README：题目大意与"用一个队列即可实现"的思路说明，英文完整版即上文关联文档。

所有题目实现都通过type TreeNode = structures.TreeNode复用公共数据结构包，避免每题重复定义节点。节点定义见 structures/TreeNode.go：

type TreeNode struct { Val int Left *TreeNode Right *TreeNode }

测试数据的构造依赖同文件中的 Ints2TreeNode：它把 LeetCode 层序数组（null位置用哨兵值NULL = -1 << 63表示，定义见 structures/TreeNode.go）还原成真正的*TreeNode。其内部同样使用一个切片模拟队列，按"父节点一次领取左右两个子节点"的方式逐位填充——这本身就是一份按层处理的模板代码，与本题解法同源。

根模块 go.mod 声明module github.com/halfrost/LeetCode-Go并通过replace指令把structures等子包指向本地目录，因此题目文件中的 import 路径（文档中写作github.com/halfrost/leetcode-go/structures，仓库实际路径为github.com/halfrost/LeetCode-Go/structures）在本地即可解析。

解法一：BFS 按层出队

// Solution 1 BFS func levelOrder(root *TreeNode) [][]int { if root == nil { return [][]int{} } queue := []*TreeNode{root} res := make([][]int, 0) for len(queue) > 0 { l := len(queue) tmp := make([]int, 0, l) for i := 0; i < l; i++ { if queue[i].Left != nil { queue = append(queue, queue[i].Left) } if queue[i].Right != nil { queue = append(queue, queue[i].Right) } tmp = append(tmp, queue[i].Val) } queue = queue[l:] res = append(res, tmp) } return res }

逐段拆解（以 leetcode/0102.Binary-Tree-Level-Order-Traversal/102. Binary Tree Level Order Traversal.go 为准）：

1. 空树处理：root == nil时直接返回[][]int{}，保证结果是"空切片"而非nil，这一点被测试用例{[]int{}, [][]int{}}覆盖。
2. 外层循环 = 逐层推进：每轮开始时l := len(queue)记录当前这一层的节点数。这是 BFS 分层的标准技巧——用入层时的队列长度作为"层边界"。
3. 内层循环 = 处理一层：只对前l个节点做处理（取值、入队子节点），本轮新 append 的子节点位于下标l之后，天然属于下一层，下一轮才会被访问。
4. queue = queue[l:]滑动窗口出队：这里没有显式队列类型，而是用切片queue模拟 FIFO：处理完一层后把前l个已消费的元素从视图上"丢掉"，只保留新子节点。从源码结构看，这与仓库公共包 structures/Queue.go 中Pop的q.nums = q.nums[1:]写法是同一套切片头偏移思想，避免 O(n) 元素搬移。
5. 预分配容量：tmp := make([]int, 0, l)按当前层节点数预留容量，减少一次层内扩容。

时间复杂度 O(n)，每个节点恰好入队出队一次；空间复杂度 O(n)，队列最宽处约为最底层节点数。

解法二：DFS 递归 + 按层下标收集

// Solution 2 DFS func levelOrder1(root *TreeNode) [][]int { var res [][]int var dfsLevel func(node *TreeNode, level int) dfsLevel = func(node *TreeNode, level int) { if node == nil { return } if len(res) == level { res = append(res, []int{node.Val}) } else { res[level] = append(res[level], node.Val) } dfsLevel(node.Left, level+1) dfsLevel(node.Right, level+1) } dfsLevel(root, 0) return res }

这个实现把"层级"显式地作为参数传递下去（见 leetcode/0102.Binary-Tree-Level-Order-Traversal/102. Binary Tree Level Order Traversal.go）：

• res[level]即第 level 层的收集桶。由于 DFS 是"先深后浅"访问的，到达某层第一个节点时len(res) == level成立，此时用append(res, []int{node.Val})为该层开桶；之后同层节点直接res[level] = append(res[level], node.Val)追加。
• 左子树先于右子树递归（dfsLevel(node.Left, level+1)在前），保证了每一层内部的左右顺序正确。
• 与 BFS 的本质差异：BFS 用队列长度划定层边界，DFS 则用递归深度天然携带层号；代价是递归栈深度等于树高，对极深（退化成链表形态）的树有栈溢出风险，而 BFS 只受队列宽度影响。两种写法在此仓库中并列给出，便于对比"迭代 + 队列"与"递归 + 深度参数"两条技术路线。

测试用例与本地验证

测试文件 102. Binary Tree Level Order Traversal_test.go 遵循仓库统一的用例结构：question102内嵌para102（入参one []int，即层序数组）与ans102（期望答案one [][]int），并定义了三个用例：

其中第三个用例正是文档中的经典示例，NULL（-1 << 63）表示[3,9,20,null,null,15,7]中节点 9 的左右两个空位。测试循环里先经structures.Ints2TreeNode(p.one)把层序数组转成树，然后分别调用levelOrder(root)打印输出并调用levelOrder1(root)执行第二解法。

仓库根目录的 gotest.sh 提供了一键覆盖率验证入口，执行go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...对全部题目包跑测试并产出单一合法的coverage.txt（仓库根目录已有历史产物 coverage.txt）。你也可以只针对本题目目录执行go test ./leetcode/0102.Binary-Tree-Level-Order-Traversal/单独验证。

小结

• LeetCode-Go 对 102 题给出了两种完整解法：BFS 用"每轮先记录队列长度、处理完后queue = queue[l:]截断"实现按层切分；DFS 用递归参数level作为res的下标实现按层分桶，两者均 O(n) 时间。
• 题目实现复用 structures 包的TreeNode与Ints2TreeNode，后者本身就以层序队列方式从数组重建二叉树，是与本题同源的模板代码。
• 全部结论可对照 题解文档、实现文件与 测试文件 逐行核验。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go