LeetCode-Go 题解104. Maximum Depth of Binary Tree二叉树最大深度递归实现与源码分析【免费下载链接】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 一题展开完整解析求二叉树最大深度这一基础树题目的题意、递归解题思路、Go 源码实现与测试用例。读完本文你将掌握二叉树深度类题目的标准递归套路分治左右子树取最大值再加一并理解 LeetCode-Go 仓库中二叉树测试数据的构造方式[]int层序转树可直接套用到 0559N 叉树最大深度、0111最小深度等同类型题目上。题目描述Given a binary tree, find its maximum depth.The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.Note: A leaf is a node with no children.Example:Given binary tree [3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7return its depth 3.题目大意要求输出一棵树的最大高度最大深度。最大深度的定义是从根节点到最远叶子节点的最长路径上的节点总数。叶子节点指没有子节点的节点。上述示例中最长路径为3 - 20 - 15或3 - 20 - 7路径上共 3 个节点因此返回 3。解题思路这一题递归遍历即可分别求出根节点左子树的高度和右子树的高度取出两者的最大值再加一加上根节点自身即为整棵树的总高度。其正确性来源于最大深度的递归结构空树根节点为nil的深度为 0非空树的深度 max(左子树深度, 右子树深度) 1。这正是典型的**分治Divide and Conquer**思路把整棵树的最大深度分解为左右子树的最大深度两个规模更小的子问题子问题与原问题同构天然适合用递归表达。源码级实现解析LeetCode-Go 仓库中本题的解法位于 leetcode/0104.Maximum-Depth-of-Binary-Tree/104. Maximum Depth of Binary Tree.go核心代码如下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 }逐行解读递归出口root nil时返回 0。空节点的深度为 0这一条件同时兜底了空树与叶子节点的左右子节点保证递归必然终止。递归体maxDepth(root.Left)与maxDepth(root.Right)分别求解左右子树深度max取二者较大值后 11表示计入当前根节点这一层。辅助函数max仓库在题解文件中内联定义了max(a, b int) int避免依赖额外的第三方库保证单文件可独立运行。TreeNode 结构来自仓库公共包题解文件第 8 行通过type TreeNode structures.TreeNode类型别名引入了仓库公共数据结构包structures中的二叉树节点其定义位于 structures/TreeNode.gotype TreeNode struct { Val int Left *TreeNode Right *TreeNode }Val为节点值Left/Right分别指向左、右孩子。LeetCode-Go 仓库中所有二叉树题目如前序/中序/后序遍历、树的序列化等均复用该结构接口与 LeetCode 官方给出的节点定义完全一致因此题解可以无缝提交。复杂度分析时间复杂度O(n)每个节点恰好被访问一次空间复杂度O(h)h 为树的高度即递归调用栈的最大深度。最坏情况链状树下 h n退化为 O(n)平均/平衡情况下为 O(log n)。测试用例与验证本题测试位于 leetcode/0104.Maximum-Depth-of-Binary-Tree/104. Maximum Depth of Binary Tree_test.go共覆盖 3 组用例输入层序数组对应树期望输出[]空树0[3, 9, 20, NULL, NULL, 15, 7]题目示例树3[1, 2, 3, 4, NULL, NULL, NULL, 5]偏斜的树4其中structures.NULL是仓库定义的占位常量用于在层序数组中标记空节点其值为-1 63见 structures/TreeNode.go。测试通过structures.Ints2TreeNode(p.one)将层序数组构造成二叉树后调用maxDepth再与期望值比对任一用例不通过都会以t.Fatalf终止。仓库中Ints2TreeNode的构造逻辑structures/TreeNode.go使用**队列按层序BFS**建树以数组首元素为根逐个为当前队首节点挂载左、右孩子遇NULL值则跳过该子节点值得对照阅读以理解测试数据的含义。第三组用例[1, 2, 3, 4, NULL, NULL, NULL, 5]构造的树结构为1 / \ 2 3 / 4 / 5最长路径1 - 2 - 4 - 5共 4 层验证了递归解法在偏向一侧的树上同样正确。如何在本地运行验证仓库根目录的 gotest.sh 提供了全量测试脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...若只想验证本题可进入 leetcode/0104.Maximum-Depth-of-Binary-Tree 目录单独执行go test -v仓库根目录 go.mod 中声明了 Go 1.19并通过replace指令将github.com/halfrost/LeetCode-Go/structures指向本地./structures目录因此题解文件可以直接复用公共数据结构而无需联网拉取依赖。延伸思考本题在仓库中的同类应用递归求深度是二叉树问题的基础模板LeetCode-Go 仓库中多处复用了这一思路0559. Maximum Depth of N-ary TreeN 叉树的最大深度把左右子树取 max推广为遍历所有孩子节点取 max0111. Minimum Depth of Binary Tree求最小深度与本题对称但需额外处理单边为空的边界情况0104 题解文件 本身也是很多递归类题目如判断平衡二叉树、计算直径等的子过程。理解 104 题的递归写法是掌握上述一系列树形递归问题的起点。除递归外本题也可用层序遍历BFS 计数层数的方式求解仓库当前提供的是递归版本这也是树深度类题目最简洁直观的标准解法。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考