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。计算从根到叶子节点生成的所有数字之和。说明叶子节点是指没有子节点的节点。示例 1Input: [1,2,3] 1 / \ 2 3 Output: 25解释根到叶子路径1-2代表数字12路径1-3代表数字13因此sum 12 13 25。示例 2Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026解释路径4-9-5代表4954-9-1代表4914-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*1044、4*10949、49*105495恰好等价于字符串拼接495。叶子节点汇总当root.Left与root.Right均为nil时说明当前节点是叶子将完整路径数字累加到*res并返回不再向下递归。3. 为何结果参数使用指针*intdfs通过指针res *int在递归调用间共享累计和。若改为值传递每次递归会复制res叶子节点的累加结果将无法回传到最外层调用。而路径数字sum使用值传递恰好利用递归栈天然隔离每条分支互不干扰。递归过程可视化以示例 1 的二叉树[1,2,3]为例dfs的执行轨迹如下dfs(1, 0) sum 0*101 1非叶子继续 ├── dfs(2, 1) sum 1*102 12叶子节点res 12 └── dfs(3, 1) sum 1*103 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 -covermodeatomic -coverprofilecoverage.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），仅供参考