LeetCode-Go 题解 1302. Deepest Leaves Sum：一次 DFS 求二叉树最深叶子节点之和

LeetCode-Go 题解 1302. Deepest Leaves Sum一次 DFS 求二叉树最深叶子节点之和【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读LeetCode 1302「Deepest Leaves Sum最深叶子之和」要求对一棵二叉树求出深度最大的一层上所有叶子节点值的总和是二叉树遍历与「层深维护」结合的经典入门题。本文以 LeetCode-Go 仓库中该题的 题解文档 为骨架结合仓库内的 Go 实现 与 测试用例完整讲解 DFS 单次遍历的解法原理、指针传参的写法细节、测试驱动验证方法并对比 BFS 层次遍历方案帮助你彻底吃透这一类「最深层求和」问题。题目回顾与约束给定一棵二叉树返回最深层深度最大的一层叶子节点的值之和。示例 1Input: root [1,2,3,4,5,null,6,7,null,null,null,null,8] Output: 15对应该示例的二叉树结构层序遍历序列1 / \ 2 3 / \ \ 4 5 6 / \ 7 8树的最大深度为 4最底层叶子节点为7与87 8 15。约束条件树中节点数目在1到10^4之间每个节点的值在1到100之间。由于节点数最大可达10^4递归 DFS 的调用栈深度与树高相关在非极端退化的输入下是安全的最坏为单链时深度约等于节点数此时需要考虑栈深度也可改用 BFS见下文进阶对比。题意分析什么是「最深的叶子」题目要的是层数最深的叶子节点的和而不是「所有叶子节点中值最大的和」也不是「所有叶子节点值之和」。核心判定条件是节点必须是叶子Left与Right均为nil该叶子所在的层必须是整棵树的最大层。因此解题的关键是在遍历过程中同时记录两个状态当前遇到的最大层深maxLevel以及该层深下累计的和sum。核心思路DFS 单次遍历边走边维护「最深」与「和」原题解文档给出的思路非常简洁这一题不难DFS 遍历把最底层的叶子节点和都加起来即可。具体策略是从根节点开始做前序 DFS每深入一层level 1对每个访问到的节点分三种情况处理level maxLevel发现更深的层说明此前记录的sum全部作废重置maxLevel level、sum root.Val当前节点是这一层的第一个节点直接作为新和level maxLevel与当前已知最深层同层累加sum root.Vallevel maxLevel不是最深层的节点直接忽略。由于我们只对叶子累加……这里需要特别说明题目要求的是叶子节点但上述策略对所有节点执行了比较与累加逻辑为什么结果是正确的原因在于最深层上的节点必然是叶子节点——如果一个节点位于最深层且还有孩子那么它的孩子所在的层更深maxLevel会被更新该节点就不会再被算入。因此「最深层的所有节点」与「最深层的所有叶子」是同一集合无需显式判断Left nil Right nil。这是一个值得记住的简化技巧。仓库源码逐步讲解仓库中的实现位于 1302. Deepest Leaves Sum.go完整代码如下func deepestLeavesSum(root *TreeNode) int { maxLevel, sum : 0, 0 dfsDeepestLeavesSum(root, 0, maxLevel, sum) return sum } func dfsDeepestLeavesSum(root *TreeNode, level int, maxLevel, sum *int) { if root nil { return } if level *maxLevel { *maxLevel, *sum level, root.Val } else if level *maxLevel { *sum root.Val } dfsDeepestLeavesSum(root.Left, level1, maxLevel, sum) dfsDeepestLeavesSum(root.Right, level1, maxLevel, sum) }逐段拆解入口函数deepestLeavesSummaxLevel, sum : 0, 0 dfsDeepestLeavesSum(root, 0, maxLevel, sum) return summaxLevel记录遍历至今遇到的最大层深sum记录该层所有节点值之和二者初值均为0根节点从level 0开始计数因为递归函数需要跨调用修改maxLevel与sum所以传入指针maxLevel、sum当树为空root nil时递归在第一步直接返回函数最终返回sum 0与测试用例中空树的期望输出0一致。递归函数dfsDeepestLeavesSumif root nil { return }空节点直接剪枝返回这是所有二叉树递归题的标准出口。if level *maxLevel { *maxLevel, *sum level, root.Val } else if level *maxLevel { *sum root.Val }这是整个算法的核心也是与「求树的最大深度」「求所有叶子之和」等题目的关键区别点进入更深一层时旧层累加值已无意义必须重置而非继续累加否则会把浅层节点的值混入结果同层时累加较浅层时什么都不做。dfsDeepestLeavesSum(root.Left, level1, maxLevel, sum) dfsDeepestLeavesSum(root.Right, level1, maxLevel, sum)递归访问左右子树层深level 1。注意这里的 DFS 对每一层的最左侧节点都会先触发level *maxLevel的重置分支。以示例树为例遍历到最底层时首先遇到节点7此时level 3 maxLevel 2于是maxLevel 3, sum 7随后遇到节点8level maxLevelsum 7 8 15。最终返回15。关键实现细节为什么maxLevel和sum要用指针Go 语言中函数参数是值传递。如果直接在递归函数内写maxLevel level、sum root.Val修改的只是当前调用帧的局部副本返回上一层后修改即丢失最终得到的sum只会是最后一次递归调用累加出的局部值结果必然错误。仓库实现通过*int指针让所有递归调用共享同一份内存dfsDeepestLeavesSum(root, 0, maxLevel, sum)在函数体内用*maxLevel、*sum解引用读写从而把「最大层深」和「累计和」这两个状态贯穿整棵树的遍历过程。这也是面试中经常被追问的一个点为什么这里必须取地址传入答案是 Go 的值传递语义要求跨调用共享可变状态时必须显式传指针。数据结构与测试工具仓库如何构造二叉树题目签名依赖TreeNode仓库在 structures/TreeNode.go 中统一定义了二叉树节点与一批测试工具// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // NULL 方便添加测试数据 var NULL -1 63测试文件通过structures.Ints2TreeNode把 LeetCode 风格的层序数组[]int其中NULL表示空节点还原成一棵真正的二叉树para1302{[]int{1, 2, 3, 4, 5, structures.NULL, 6, 7, structures.NULL, structures.NULL, structures.NULL, structures.NULL, 8}}Ints2TreeNode的实现见 structures/TreeNode.go L19-L51使用队列做 BFS 建树取数组首元素作根随后按层序把非NULL的值挂到当前节点的左右孩子上NULL位置则跳过孩子保持nil。这是理解测试数据如何映射为真实树结构的关键。测试与验证仓库的测试用例位于 1302. Deepest Leaves Sum_test.go覆盖了两个场景输入层序数组期望输出说明[1,2,3,4,5,null,6,7,null,null,null,null,8]15题目给出的标准示例最深层为7 8[]空树0边界情况无节点时和为0测试通过structures.Ints2TreeNode(p.one)构造根节点后直接调用deepestLeavesSum并打印输入输出便于人工核对。仓库根目录的 gotest.sh 提供了统一运行全部测试的命令go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只针对本题运行go test -v ./leetcode/1302.Deepest-Leaves-Sum/复杂度分析时间复杂度O(n)其中n为节点数。每个节点恰好被访问一次比较与累加均为 O(1)空间复杂度O(h)h为树高对应递归调用栈深度最坏情况单链树为 O(n)平均/平衡树为 O(log n)。这与原题解文档的「DFS 遍历把最底层叶子节点和都加起来」的思路完全一致是线性时间内可解的最优复杂度。进阶对比BFS 层次遍历的另一条路径除 DFS 外本题还有经典的BFS 层次遍历解法按层逐层遍历每进入新的一层就重置sum为 0处理完该层所有节点后再进入下一层最后一层遍历结束时sum即为答案。两种方案对比维度DFS本题仓库实现BFS 层次遍历遍历顺序前序递归深度优先队列辅助逐层扫描状态维护maxLevelsum指针跨调用共享每层重置sum天然知道当前层空间占用O(h) 递归栈O(w)w为最大层宽最坏 O(n)理解难度需要理解指针共享状态与「最深即叶子」的简化直观但需额外处理层边界DFS 的写法更简洁代码量更少BFS 则在树极深如10^4个节点退化成单链时能避免递归栈溢出的风险。两者在 LeetCode-Go 仓库的同类树题中都有广泛应用可根据面试场景灵活选择。小结LeetCode 1302「Deepest Leaves Sum」是一道考察二叉树遍历与全局状态维护的经典题目。通过 LeetCode-Go 仓库的这份题解可以掌握三个核心知识点一次 DFS 完成「找最深层 求该层和」两个目标核心是level maxLevel时重置、level maxLevel时累加Go 指针传参在递归共享状态中的必要性这是容易出错也常被面试追问的实现细节「最深层节点必然是叶子」的简化结论省去了显式的叶子判断。配合仓库的测试用例与structures工具Ints2TreeNode、Tree2ints你可以直接运行go test验证实现并将同一套 DFS 状态维护思路迁移到「最深层平均值」「最深层最大值」等衍生题目上。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考