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包含三个文件解法实现levelOrderBFS与levelOrder1DFS两个函数测试文件定义question102用例并驱动两个解法运行中文题解 README题目大意与用一个队列即可实现的思路说明英文完整版即上文关联文档。所有题目实现都通过type TreeNode structures.TreeNode复用公共数据结构包避免每题重复定义节点。节点定义见 structures/TreeNode.gotype 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 为准空树处理root nil时直接返回[][]int{}保证结果是空切片而非nil这一点被测试用例{[]int{}, [][]int{}}覆盖。外层循环 逐层推进每轮开始时l : len(queue)记录当前这一层的节点数。这是 BFS 分层的标准技巧——用入层时的队列长度作为层边界。内层循环 处理一层只对前l个节点做处理取值、入队子节点本轮新 append 的子节点位于下标l之后天然属于下一层下一轮才会被访问。queue queue[l:]滑动窗口出队这里没有显式队列类型而是用切片queue模拟 FIFO处理完一层后把前l个已消费的元素从视图上丢掉只保留新子节点。从源码结构看这与仓库公共包 structures/Queue.go 中Pop的q.nums q.nums[1:]写法是同一套切片头偏移思想避免 O(n) 元素搬移。预分配容量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, level1) dfsLevel(node.Right, level1) } dfsLevel(root, 0) return res }这个实现把层级显式地作为参数传递下去见 leetcode/0102.Binary-Tree-Level-Order-Traversal/102. Binary Tree Level Order Traversal.gores[level]即第 level 层的收集桶。由于 DFS 是先深后浅访问的到达某层第一个节点时len(res) level成立此时用append(res, []int{node.Val})为该层开桶之后同层节点直接res[level] append(res[level], node.Val)追加。左子树先于右子树递归dfsLevel(node.Left, level1)在前保证了每一层内部的左右顺序正确。与 BFS 的本质差异BFS 用队列长度划定层边界DFS 则用递归深度天然携带层号代价是递归栈深度等于树高对极深退化成链表形态的树有栈溢出风险而 BFS 只受队列宽度影响。两种写法在此仓库中并列给出便于对比迭代 队列与递归 深度参数两条技术路线。测试用例与本地验证测试文件 102. Binary Tree Level Order Traversal_test.go 遵循仓库统一的用例结构question102内嵌para102入参one []int即层序数组与ans102期望答案one [][]int并定义了三个用例输入层序数组期望输出[][][]int{}[1][[1]][3, 9, 20, NULL, NULL, 15, 7][[3], [9, 20], [15, 7]]其中第三个用例正是文档中的经典示例NULL-1 63表示[3,9,20,null,null,15,7]中节点 9 的左右两个空位。测试循环里先经structures.Ints2TreeNode(p.one)把层序数组转成树然后分别调用levelOrder(root)打印输出并调用levelOrder1(root)执行第二解法。仓库根目录的 gotest.sh 提供了一键覆盖率验证入口执行go test -covermodeatomic -coverprofilecoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 102 二叉树层序遍历：LeetCode-Go 中基于队列的 BFS 与 DFS 分层两种解法
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包含三个文件解法实现levelOrderBFS与levelOrder1DFS两个函数测试文件定义question102用例并驱动两个解法运行中文题解 README题目大意与用一个队列即可实现的思路说明英文完整版即上文关联文档。所有题目实现都通过type TreeNode structures.TreeNode复用公共数据结构包避免每题重复定义节点。节点定义见 structures/TreeNode.gotype 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 为准空树处理root nil时直接返回[][]int{}保证结果是空切片而非nil这一点被测试用例{[]int{}, [][]int{}}覆盖。外层循环 逐层推进每轮开始时l : len(queue)记录当前这一层的节点数。这是 BFS 分层的标准技巧——用入层时的队列长度作为层边界。内层循环 处理一层只对前l个节点做处理取值、入队子节点本轮新 append 的子节点位于下标l之后天然属于下一层下一轮才会被访问。queue queue[l:]滑动窗口出队这里没有显式队列类型而是用切片queue模拟 FIFO处理完一层后把前l个已消费的元素从视图上丢掉只保留新子节点。从源码结构看这与仓库公共包 structures/Queue.go 中Pop的q.nums q.nums[1:]写法是同一套切片头偏移思想避免 O(n) 元素搬移。预分配容量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, level1) dfsLevel(node.Right, level1) } dfsLevel(root, 0) return res }这个实现把层级显式地作为参数传递下去见 leetcode/0102.Binary-Tree-Level-Order-Traversal/102. Binary Tree Level Order Traversal.gores[level]即第 level 层的收集桶。由于 DFS 是先深后浅访问的到达某层第一个节点时len(res) level成立此时用append(res, []int{node.Val})为该层开桶之后同层节点直接res[level] append(res[level], node.Val)追加。左子树先于右子树递归dfsLevel(node.Left, level1)在前保证了每一层内部的左右顺序正确。与 BFS 的本质差异BFS 用队列长度划定层边界DFS 则用递归深度天然携带层号代价是递归栈深度等于树高对极深退化成链表形态的树有栈溢出风险而 BFS 只受队列宽度影响。两种写法在此仓库中并列给出便于对比迭代 队列与递归 深度参数两条技术路线。测试用例与本地验证测试文件 102. Binary Tree Level Order Traversal_test.go 遵循仓库统一的用例结构question102内嵌para102入参one []int即层序数组与ans102期望答案one [][]int并定义了三个用例输入层序数组期望输出[][][]int{}[1][[1]][3, 9, 20, NULL, NULL, 15, 7][[3], [9, 20], [15, 7]]其中第三个用例正是文档中的经典示例NULL-1 63表示[3,9,20,null,null,15,7]中节点 9 的左右两个空位。测试循环里先经structures.Ints2TreeNode(p.one)把层序数组转成树然后分别调用levelOrder(root)打印输出并调用levelOrder1(root)执行第二解法。仓库根目录的 gotest.sh 提供了一键覆盖率验证入口执行go test -covermodeatomic -coverprofilecoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考