LeetCode 129 Sum Root to Leaf Numbers 题解：基于 Go 前序遍历的根到叶子数字求和
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
本文围绕 LeetCode 第 129 题「Sum Root to Leaf Numbers（求根到叶子节点数字之和）」展开，以 LeetCode-Go 仓库中 0129.Sum-Root-to-Leaf-Numbers 题解文档为主体，结合仓库内的 Go 源码与单元测试，深入讲解二叉树前序遍历、路径数字拼接与递归汇总的实现原理。读完本文，你将掌握这类"沿路径累积数值、在叶子节点汇总"问题的标准递归模板，并能直接复用仓库中的 TreeNode 构造与测试基础设施进行验证。
题目描述
给定一个二叉树，它的每个结点都存放一个0-9的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径1->2->3代表数字123。
计算从根到叶子节点生成的所有数字之和。
说明：叶子节点是指没有子节点的节点。
示例 1
Input: [1,2,3] 1 / \ 2 3 Output: 25解释：根到叶子路径1->2代表数字12，路径1->3代表数字13，因此sum = 12 + 13 = 25。
示例 2
Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026解释：路径4->9->5代表495，4->9->1代表491，4->0代表40，因此sum = 495 + 491 + 40 = 1026。
解题思路：前序遍历 + 路径数字累积
本题的核心思想是前序遍历：从根节点出发，沿着每条分支一路走到叶子节点，在途中持续"拼接"路径数字，并在每个叶子节点处将完整数字累加到最终结果中。
由于题目保证每个结点只存放0-9的数字，路径数字的拼接可以用纯算术运算完成，无需字符串转换：当前节点的路径数字等于父路径数字 × 10 + 当前节点值。这样当递归到达叶子节点时，sum中保存的正是这条根到叶子路径对应的完整整数。
Go 源码实现详解
仓库在 129. Sum Root to Leaf Numbers.go 中给出了完整实现：
package leetcode import ( "github.com/halfrost/LeetCode-Go/structures" ) // TreeNode define type TreeNode = structures.TreeNode func sumNumbers(root *TreeNode) int { res := 0 dfs(root, 0, &res) return res } func dfs(root *TreeNode, sum int, res *int) { if root == nil { return } sum = sum*10 + root.Val if root.Left == nil && root.Right == nil { *res += sum return } dfs(root.Left, sum, res) dfs(root.Right, sum, res) }逐行拆解
1. 类型别名与入口函数
文件顶部通过type TreeNode = structures.TreeNode将仓库公共模块 structures/TreeNode.go 中定义的树节点结构直接复用到本题：
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }入口函数sumNumbers负责初始化结果变量res并以0作为初始路径数字启动递归，最终返回累计和。
2. 递归函数dfs的三个关键步骤
- 空节点兜底：
root == nil时直接返回。这是递归的安全退出条件，保证对空树或单分支缺失的子树调用不会越界。 - 路径数字拼接：
sum = sum*10 + root.Val是核心递推式。以示例 2 为例，路径4 -> 9 -> 5依次计算为0*10+4=4、4*10+9=49、49*10+5=495，恰好等价于字符串拼接"4"+"9"+"5"。 - 叶子节点汇总：当
root.Left与root.Right均为nil时，说明当前节点是叶子，将完整路径数字累加到*res并返回，不再向下递归。
3. 为何结果参数使用指针*int
dfs通过指针res *int在递归调用间共享累计和。若改为值传递，每次递归会复制res，叶子节点的累加结果将无法回传到最外层调用。而路径数字sum使用值传递，恰好利用递归栈天然隔离每条分支，互不干扰。
递归过程可视化
以示例 1 的二叉树[1,2,3]为例，dfs的执行轨迹如下：
dfs(1, 0) sum = 0*10+1 = 1，非叶子，继续 ├── dfs(2, 1) sum = 1*10+2 = 12，叶子节点，res += 12 └── dfs(3, 1) sum = 1*10+3 = 13，叶子节点，res += 13 最终 res = 12 + 13 = 25可见每次从左子树返回时，路径数字自动恢复为父节点的值，这正是"值传递 + 深度优先回溯"带来的天然特性。
复杂度分析
- 时间复杂度：
O(n)，其中n为二叉树节点数。每个节点恰好被访问一次。 - 空间复杂度：
O(h)，h为树的高度，即递归调用栈的深度。最坏情况（树退化为单链表）下为O(n)，平衡二叉树下为O(log n)。
单元测试与验证
仓库为本题编写了完整的表驱动测试，位于 129. Sum Root to Leaf Numbers_test.go，测试用例覆盖了三种典型场景：
| 输入（层序遍历数组） | 期望输出 | 覆盖场景 |
|---|---|---|
[] | 0 | 空树边界 |
[1,2,3] | 25 | 题目示例 1 |
[4,9,0,5,1] | 1026 | 题目示例 2，含三节点深路径 |
测试通过structures.Ints2TreeNode将层序数组一键还原为二叉树：
root := structures.Ints2TreeNode(p.one) fmt.Printf("【output】:%v \n", sumNumbers(root))Ints2TreeNode在 structures/TreeNode.go 中实现，采用队列逐层构建的方式：以数组首元素为根，按层序依次为每个节点挂载左右孩子，数组中用常量NULL = -1 << 63表示空位。这也是整个 LeetCode-Go 仓库大量二叉树题解共用的测试基建，可直接复用。
在仓库根目录执行测试命令即可验证本题实现（该命令来自 gotest.sh 的包级测试写法）：
go test ./leetcode/0129.Sum-Root-to-Leaf-Numbers/...若需连同覆盖率统计，可执行：
go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/0129.Sum-Root-to-Leaf-Numbers/...边界情况与易错点
- 空树：输入
nil时，sumNumbers中的dfs(root, 0, &res)直接命中root == nil分支返回，结果保持0，不会发生空指针解引用。 - 单节点树：根节点本身就是叶子，
sum = root.Val后直接累加，结果即根节点值。 - 值为 0 的节点：由于拼接采用
sum*10 + root.Val，中间节点为0时（如示例 2 的路径4->0得40）不会丢失数字位，算术拼接天然正确处理。 - 不要忘记
return位置：叶子节点累加后必须立即return，否则会继续访问nil子节点；尽管空节点分支会兜底，但提前返回可避免无意义的递归调用，语义也更清晰。
思路推广：同类问题的通用模板
本题的"前序遍历 + 路径累积 + 叶子汇总"模板具有很好的泛化能力，同一仓库中多个题解采用了类似结构：
- Path Sum：同样前序遍历，在叶子节点判断路径和是否等于
targetSum。 - Path Sum II：在本题基础上多维护一条路径切片，叶子节点处将满足条件的路径快照存入结果集。
- Sum Root to Leaf Numbers 的变体通常还会在
sum上取模，对应 LeetCode 上对大数求和的同类题目。
掌握sum = sum*10 + root.Val这一递推式与"叶子判定"的时机，即可举一反三应对各类"根到叶子路径问题"。
总结
LeetCode 129 是一道典型的二叉树 DFS 应用题。仓库给出的解法以前序遍历为骨架，用一行递推式sum = sum*10 + root.Val完成路径数字拼接，在叶子节点处累加汇总，配合指针型结果参数实现跨递归层的数据共享，整体实现简洁、正确性高，并配套了完整的表驱动测试用例。无论是面试手写还是日常刷题复盘，都可以直接参考 源码实现 与其 测试文件 作为模板。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
