企业官网建设流程全解析

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 层次遍历方案，帮助你彻底吃透这一类「最深层求和」问题。

题目回顾与约束

给定一棵二叉树，返回最深层（深度最大的一层）叶子节点的值之和。

示例 1：

Input: 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与8，7 + 8 = 15。

约束条件：

• 树中节点数目在1到10^4之间；
• 每个节点的值在1到100之间。

由于节点数最大可达10^4，递归 DFS 的调用栈深度与树高相关；在非极端退化的输入下是安全的（最坏为单链时深度约等于节点数，此时需要考虑栈深度，也可改用 BFS，见下文进阶对比）。

题意分析：什么是「最深的叶子」

题目要的是层数最深的叶子节点的和，而不是「所有叶子节点中值最大的和」，也不是「所有叶子节点值之和」。核心判定条件是：

1. 节点必须是叶子（Left与Right均为nil）；
2. 该叶子所在的层必须是整棵树的最大层。

因此解题的关键是在遍历过程中同时记录两个状态：当前遇到的最大层深maxLevel，以及该层深下累计的和sum。

核心思路：DFS 单次遍历，边走边维护「最深」与「和」

原题解文档给出的思路非常简洁：

这一题不难，DFS 遍历把最底层的叶子节点和都加起来即可。

具体策略是：从根节点开始做前序 DFS，每深入一层level + 1，对每个访问到的节点分三种情况处理：

• level > maxLevel：发现更深的层，说明此前记录的sum全部作废，重置maxLevel = level、sum = root.Val（当前节点是这一层的第一个节点，直接作为新和）；
• level == maxLevel：与当前已知最深层同层，累加sum += root.Val；
• level < 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, level+1, maxLevel, sum) dfsDeepestLeavesSum(root.Right, level+1, maxLevel, sum) }

逐段拆解：

入口函数deepestLeavesSum

maxLevel, sum := 0, 0 dfsDeepestLeavesSum(root, 0, &maxLevel, &sum) return sum

• maxLevel记录遍历至今遇到的最大层深，sum记录该层所有节点值之和，二者初值均为0；
• 根节点从level = 0开始计数；
• 因为递归函数需要跨调用修改maxLevel与sum，所以传入指针（&maxLevel、&sum）；
• 当树为空（root == nil）时，递归在第一步直接返回，函数最终返回sum = 0，与测试用例中空树的期望输出0一致。

递归函数dfsDeepestLeavesSum

if root == nil { return }

空节点直接剪枝返回，这是所有二叉树递归题的标准出口。

if level > *maxLevel { *maxLevel, *sum = level, root.Val } else if level == *maxLevel { *sum += root.Val }

这是整个算法的核心，也是与「求树的最大深度」「求所有叶子之和」等题目的关键区别点：

• 进入更深一层时，旧层累加值已无意义，必须重置而非继续累加，否则会把浅层节点的值混入结果；
• 同层时累加；
• 较浅层时什么都不做。

dfsDeepestLeavesSum(root.Left, level+1, maxLevel, sum) dfsDeepestLeavesSum(root.Right, level+1, maxLevel, sum)

递归访问左右子树，层深level + 1。

注意：这里的 DFS 对每一层的最左侧节点都会先触发level > *maxLevel的重置分支。以示例树为例，遍历到最底层时，首先遇到节点7，此时level = 3 > maxLevel = 2，于是maxLevel = 3, sum = 7；随后遇到节点8，level == maxLevel，sum = 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 tree's 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，覆盖了两个场景：

测试通过structures.Ints2TreeNode(p.one)构造根节点后直接调用deepestLeavesSum，并打印输入输出便于人工核对。

仓库根目录的 gotest.sh 提供了统一运行全部测试的命令：

go test -covermode=atomic -coverprofile=coverage.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 则在树极深（如10^4个节点退化成单链）时能避免递归栈溢出的风险。两者在 LeetCode-Go 仓库的同类树题中都有广泛应用，可根据面试场景灵活选择。

小结

LeetCode 1302「Deepest Leaves Sum」是一道考察二叉树遍历与全局状态维护的经典题目。通过 LeetCode-Go 仓库的这份题解，可以掌握三个核心知识点：

1. 一次 DFS 完成「找最深层 + 求该层和」两个目标，核心是level > maxLevel时重置、level == maxLevel时累加；
2. Go 指针传参在递归共享状态中的必要性，这是容易出错也常被面试追问的实现细节；
3. 「最深层节点必然是叶子」的简化结论，省去了显式的叶子判断。

配合仓库的测试用例与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