尧图网站建设 
LeetCode-Go 第 104 题「二叉树的最大深度」题解递归遍历、测试数据构造与覆盖率验证【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇围绕 LeetCode-Go 仓库中 104. Maximum Depth of Binary Tree 的官方题解文档展开先完整继承文档中的问题定义与递归思路再对照仓库中实际的题解源码、测试用例与structures包工具函数讲清楚这道经典二叉树题目在 Go 中的实现细节、测试数据的构造方式以及如何在本地运行并验证 100% 覆盖率。读完本文你可以掌握二叉树深度的递归递推关系、nil基准情形base case的必要性、如何用层序数组含哨兵值在测试中快速构造二叉树以及该仓库「每道题独立目录 表驱动测试 统一覆盖率脚本」的工程化组织方式。一、问题定义什么是二叉树的最大深度根据关联文档给出的题目描述给定一棵二叉树求它的最大深度maximum depth。最大深度定义为从根节点到最远叶子节点的最长路径上所经过的节点数。文档特别注明叶子节点leaf是指没有子节点的节点。文档中的示例输入是层序表示[3,9,20,null,null,15,7]3 / \ 9 20 / \ 15 7该树最长路径为3 - 20 - 15或3 - 20 - 7共 3 个节点因此答案返回3。这里有一个容易混淆的细节值得明确「深度」计数的是节点个数而非边的条数所以单节点树的深度是 1空树的深度是 0。这一点直接决定了递归实现中「加 1」和「基准情形返回 0」的写法。二、解题思路后序递归求两子树高度取较大者再 1文档给出的解题思路Solution Approach是这一题用递归遍历即可——分别求出根节点左孩子的高度与右孩子的高度取两者的最大值再加一即为总高度。把这个思路写成递推关系就是基准情形若当前节点为nil即空子树高度为0递推关系height(root) max(height(root.Left), height(root.Right)) 1。这是一种典型的**自底向上后序**递归当前节点的高度必须依赖左右子树的结果所以先递归到叶子再逐层返回。nil返回 0 的基准情形同时覆盖了两种边界整棵树为空答案 0以及叶子节点左右都是nil答案为max(0, 0) 1 1不需要单独判断叶子。三、完整 Go 实现对照仓库源码题解文档给出的核心代码如下func maxDepth(root *TreeNode) int { if root nil { return 0 } return max(maxDepth(root.Left), maxDepth(root.Right)) 1 }仓库中对应的完整题解文件是 104. Maximum Depth of Binary Tree.go在文档代码之外还包含两处工程化细节import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode func maxDepth(root *TreeNode) int { if root nil { return 0 } return max(maxDepth(root.Left), maxDepth(root.Right)) 1 } func max(a int, b int) int { if a b { return a } return b }有两点值得注意节点类型来自公共包。题解中TreeNode是一个类型别名指向 structures.TreeNode// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }所有二叉树题目共享这一份节点定义各题解文件内只需type TreeNode structures.TreeNode一行别名保持与 LeetCode 官方题目注释中的节点结构一致。自定义了max辅助函数题解文件第 26-31 行。该仓库支持较早的 Go 版本不能直接使用 Go 1.21 引入的内建max因此题目包内自行实现了这个二元最大值函数。这也解释了文档代码中max(...)并非魔法函数而是同包内定义的普通函数。复杂度分析设树的节点数为n、高度为h时间复杂度 O(n)每个节点恰好被访问一次maxDepth对每个节点做常数次比较与加法空间复杂度 O(h)来自递归调用栈的深度。对平衡二叉树h O(log n)对退化成链的最坏情形h O(n)。如果不想依赖递归栈也可以采用按层遍历BFS的迭代方式用队列逐层展开队列非空时层数加一直到遍历完所有节点。两种方式的时间复杂度都是 O(n)本题文档给出的递归版本胜在代码最短、最贴合「高度 子树高度取大 1」的数学定义。四、测试体系哨兵 NULL 与层序数组构建树这道题在仓库中的测试文件是 104. Maximum Depth of Binary Tree_test.go它体现了 LeetCode-Go 统一的表驱动测试风格定义question104结构体内嵌参数结构体para104与答案结构体ans104再把所有测试用例放进切片循环执行。测试用例共有 3 组测试文件第 29-45 行输入层序数组期望输出覆盖点[]0空树root nil基准情形[3, 9, 20, NULL, NULL, 15, 7]3文档中的标准示例含null空洞[1, 2, 3, 4, NULL, NULL, NULL, 5]4深度为 4 的偏斜树验证多层递归这里的NULL是structures包定义的哨兵常量structures/TreeNode.go 第 16 行// NULL 方便添加测试数据 var NULL -1 63即int64最小值math.MinInt64用于在层序数组中占位表示「该位置没有节点」。测试执行时每个用例的输入数组都会先通过structures.Ints2TreeNode转换成真正的二叉树再传入maxDepth断言root : structures.Ints2TreeNode(p.one) got : maxDepth(root) if got ! a.one { t.Fatalf(input: %v, expected: %v, got: %v, p.one, a.one, got) }Ints2TreeNode层序数组到二叉树的转换structures/TreeNode.go 第 19-51 行 的Ints2TreeNode是这套测试基础设施的核心它的实现本身就是一个 BFS 过程// Ints2TreeNode 利用 []int 生成 *TreeNode func Ints2TreeNode(ints []int) *TreeNode { n : len(ints) if n 0 { return nil } root : TreeNode{ Val: ints[0], } queue : make([]*TreeNode, 1, n*2) queue[0] root i : 1 for i n { node : queue[0] queue queue[1:] if i n ints[i] ! NULL { node.Left TreeNode{Val: ints[i]} queue append(queue, node.Left) } i if i n ints[i] ! NULL { node.Right TreeNode{Val: ints[i]} queue append(queue, node.Right) } i } return root }算法逻辑用队列维护「等待挂载子节点的节点」按层序顺序依次为当前队头节点挂左孩子、右孩子遇到NULL就跳过且不入队从而与 LeetCode 的层序序列化格式严格对应。以第三组用例[1, 2, 3, 4, NULL, NULL, NULL, 5]为例转换过程是1的左右孩子为2、32的左孩子为4、右孩子为空3的两个孩子均为空最后5挂到队列中下一个节点4的左孩子位置。得到的树有一条1 - 2 - 4 - 5的四级路径因此期望深度为 4——这正好验证了递归在「左深右浅」偏斜结构上的正确性。五、如何运行与验证在仓库根目录下可以单独运行本题的测试go test -v ./leetcode/0104.Maximum-Depth-of-Binary-Tree/测试会通过fmt.Printf打印每个用例的输入与输出例如标准用例会输出【input】:[3 9 20 -9223372036854775808 -9223372036854775808 15 7]与【output】:3任何与期望不符的用例会以t.Fatalf中断并报出input / expected / got三元组。如果希望验证整个仓库的覆盖率仓库提供了 gotest.sh 脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...它对leetcode/下所有题目包一次性生成单一合法的coverage.txt脚本注释中说明了这样写是为避免按包分别生成再cat拼接导致多个mode: atomic头、被严格解析器判为 0% 覆盖率的问题。本题的题解函数maxDepth与辅助函数max的每个分支都被上述 3 组用例覆盖到这正是该仓库宣称 100% 测试覆盖率的落地方式之一。六、小结算法层面第 104 题是「自底向上递归」的样板题——空树返回 0否则取左右子树深度的较大值加 1时间 O(n)递归栈空间 O(h)。工程层面从 题解目录 可以看到该仓库「一题一目录」的规范README.md承载中英对照题面与思路.go文件是可编译的解法_test.go用表驱动用例 structures.Ints2TreeNode/structures.NULL完成数据构造与断言。掌握这套模式后仓库中第 100-199 章其余二叉树题目如 104 题解文档 所在的 ChapterFour 目录都可以按同样的递归骨架、同样的测试基础设施去实现和验证。【免费下载链接】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 第 104 题「二叉树的最大深度」题解：递归遍历、测试数据构造与覆盖率验证
LeetCode-Go 第 104 题「二叉树的最大深度」题解递归遍历、测试数据构造与覆盖率验证【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇围绕 LeetCode-Go 仓库中 104. Maximum Depth of Binary Tree 的官方题解文档展开先完整继承文档中的问题定义与递归思路再对照仓库中实际的题解源码、测试用例与structures包工具函数讲清楚这道经典二叉树题目在 Go 中的实现细节、测试数据的构造方式以及如何在本地运行并验证 100% 覆盖率。读完本文你可以掌握二叉树深度的递归递推关系、nil基准情形base case的必要性、如何用层序数组含哨兵值在测试中快速构造二叉树以及该仓库「每道题独立目录 表驱动测试 统一覆盖率脚本」的工程化组织方式。一、问题定义什么是二叉树的最大深度根据关联文档给出的题目描述给定一棵二叉树求它的最大深度maximum depth。最大深度定义为从根节点到最远叶子节点的最长路径上所经过的节点数。文档特别注明叶子节点leaf是指没有子节点的节点。文档中的示例输入是层序表示[3,9,20,null,null,15,7]3 / \ 9 20 / \ 15 7该树最长路径为3 - 20 - 15或3 - 20 - 7共 3 个节点因此答案返回3。这里有一个容易混淆的细节值得明确「深度」计数的是节点个数而非边的条数所以单节点树的深度是 1空树的深度是 0。这一点直接决定了递归实现中「加 1」和「基准情形返回 0」的写法。二、解题思路后序递归求两子树高度取较大者再 1文档给出的解题思路Solution Approach是这一题用递归遍历即可——分别求出根节点左孩子的高度与右孩子的高度取两者的最大值再加一即为总高度。把这个思路写成递推关系就是基准情形若当前节点为nil即空子树高度为0递推关系height(root) max(height(root.Left), height(root.Right)) 1。这是一种典型的**自底向上后序**递归当前节点的高度必须依赖左右子树的结果所以先递归到叶子再逐层返回。nil返回 0 的基准情形同时覆盖了两种边界整棵树为空答案 0以及叶子节点左右都是nil答案为max(0, 0) 1 1不需要单独判断叶子。三、完整 Go 实现对照仓库源码题解文档给出的核心代码如下func maxDepth(root *TreeNode) int { if root nil { return 0 } return max(maxDepth(root.Left), maxDepth(root.Right)) 1 }仓库中对应的完整题解文件是 104. Maximum Depth of Binary Tree.go在文档代码之外还包含两处工程化细节import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode func maxDepth(root *TreeNode) int { if root nil { return 0 } return max(maxDepth(root.Left), maxDepth(root.Right)) 1 } func max(a int, b int) int { if a b { return a } return b }有两点值得注意节点类型来自公共包。题解中TreeNode是一个类型别名指向 structures.TreeNode// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }所有二叉树题目共享这一份节点定义各题解文件内只需type TreeNode structures.TreeNode一行别名保持与 LeetCode 官方题目注释中的节点结构一致。自定义了max辅助函数题解文件第 26-31 行。该仓库支持较早的 Go 版本不能直接使用 Go 1.21 引入的内建max因此题目包内自行实现了这个二元最大值函数。这也解释了文档代码中max(...)并非魔法函数而是同包内定义的普通函数。复杂度分析设树的节点数为n、高度为h时间复杂度 O(n)每个节点恰好被访问一次maxDepth对每个节点做常数次比较与加法空间复杂度 O(h)来自递归调用栈的深度。对平衡二叉树h O(log n)对退化成链的最坏情形h O(n)。如果不想依赖递归栈也可以采用按层遍历BFS的迭代方式用队列逐层展开队列非空时层数加一直到遍历完所有节点。两种方式的时间复杂度都是 O(n)本题文档给出的递归版本胜在代码最短、最贴合「高度 子树高度取大 1」的数学定义。四、测试体系哨兵 NULL 与层序数组构建树这道题在仓库中的测试文件是 104. Maximum Depth of Binary Tree_test.go它体现了 LeetCode-Go 统一的表驱动测试风格定义question104结构体内嵌参数结构体para104与答案结构体ans104再把所有测试用例放进切片循环执行。测试用例共有 3 组测试文件第 29-45 行输入层序数组期望输出覆盖点[]0空树root nil基准情形[3, 9, 20, NULL, NULL, 15, 7]3文档中的标准示例含null空洞[1, 2, 3, 4, NULL, NULL, NULL, 5]4深度为 4 的偏斜树验证多层递归这里的NULL是structures包定义的哨兵常量structures/TreeNode.go 第 16 行// NULL 方便添加测试数据 var NULL -1 63即int64最小值math.MinInt64用于在层序数组中占位表示「该位置没有节点」。测试执行时每个用例的输入数组都会先通过structures.Ints2TreeNode转换成真正的二叉树再传入maxDepth断言root : structures.Ints2TreeNode(p.one) got : maxDepth(root) if got ! a.one { t.Fatalf(input: %v, expected: %v, got: %v, p.one, a.one, got) }Ints2TreeNode层序数组到二叉树的转换structures/TreeNode.go 第 19-51 行 的Ints2TreeNode是这套测试基础设施的核心它的实现本身就是一个 BFS 过程// Ints2TreeNode 利用 []int 生成 *TreeNode func Ints2TreeNode(ints []int) *TreeNode { n : len(ints) if n 0 { return nil } root : TreeNode{ Val: ints[0], } queue : make([]*TreeNode, 1, n*2) queue[0] root i : 1 for i n { node : queue[0] queue queue[1:] if i n ints[i] ! NULL { node.Left TreeNode{Val: ints[i]} queue append(queue, node.Left) } i if i n ints[i] ! NULL { node.Right TreeNode{Val: ints[i]} queue append(queue, node.Right) } i } return root }算法逻辑用队列维护「等待挂载子节点的节点」按层序顺序依次为当前队头节点挂左孩子、右孩子遇到NULL就跳过且不入队从而与 LeetCode 的层序序列化格式严格对应。以第三组用例[1, 2, 3, 4, NULL, NULL, NULL, 5]为例转换过程是1的左右孩子为2、32的左孩子为4、右孩子为空3的两个孩子均为空最后5挂到队列中下一个节点4的左孩子位置。得到的树有一条1 - 2 - 4 - 5的四级路径因此期望深度为 4——这正好验证了递归在「左深右浅」偏斜结构上的正确性。五、如何运行与验证在仓库根目录下可以单独运行本题的测试go test -v ./leetcode/0104.Maximum-Depth-of-Binary-Tree/测试会通过fmt.Printf打印每个用例的输入与输出例如标准用例会输出【input】:[3 9 20 -9223372036854775808 -9223372036854775808 15 7]与【output】:3任何与期望不符的用例会以t.Fatalf中断并报出input / expected / got三元组。如果希望验证整个仓库的覆盖率仓库提供了 gotest.sh 脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...它对leetcode/下所有题目包一次性生成单一合法的coverage.txt脚本注释中说明了这样写是为避免按包分别生成再cat拼接导致多个mode: atomic头、被严格解析器判为 0% 覆盖率的问题。本题的题解函数maxDepth与辅助函数max的每个分支都被上述 3 组用例覆盖到这正是该仓库宣称 100% 测试覆盖率的落地方式之一。六、小结算法层面第 104 题是「自底向上递归」的样板题——空树返回 0否则取左右子树深度的较大值加 1时间 O(n)递归栈空间 O(h)。工程层面从 题解目录 可以看到该仓库「一题一目录」的规范README.md承载中英对照题面与思路.go文件是可编译的解法_test.go用表驱动用例 structures.Ints2TreeNode/structures.NULL完成数据构造与断言。掌握这套模式后仓库中第 100-199 章其余二叉树题目如 104 题解文档 所在的 ChapterFour 目录都可以按同样的递归骨架、同样的测试基础设施去实现和验证。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考