LeetCode-Go 实战LeetCode 129 根到叶数字之和的递归累加解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中 129. Sum Root to Leaf Numbers 题解文档 展开完整讲解根到叶路径数字求和这道经典二叉树题目的题意、两个标准示例、前序遍历累加的解题思路与完整 Go 实现并结合仓库源码分析sum sum*10 root.Val这一核心技巧的实现细节、测试用例的覆盖方式与本地运行验证方法。读完后你能掌握在递归遍历中携带累加状态、于叶子节点统一结算这一通用模式并能直接复用其解决路径拼接类问题如 LeetCode 257 二叉树路径。题目描述给定一个二叉树它的每个结点都存放一个0-9的数字每条从根到叶子节点的路径都代表一个数字。例如从根到叶子节点路径1-2-3代表数字123。计算从根到叶子节点生成的所有数字之和。注意叶子节点是指没有子节点的节点。示例 1Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: 路径 1-2 表示数字 12 路径 1-3 表示数字 13 因此 sum 12 13 25示例 2Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026 Explanation: 路径 4-9-5 表示数字 495 路径 4-9-1 表示数字 491 路径 4-0 表示数字 40 因此 sum 495 491 40 1026解题思路前序遍历 路径累加题解文档给出的核心思路是运用前序遍历的思想从根节点出发一路累加直到叶子节点时汇总一次最后返回所有叶子节点汇总的总和。文档同时指出本题是 LeetCode 257 二叉树路径 的变体257 要求输出每条从根到叶的路径而本题把每条路径上的数字拼接成一个十进制整数后累加。两者的遍历骨架完全一致区别只在于路径上的处理动作不同——257 是拼接字符串129 是做十进制位移累加。实现上有两个关键设计十进制移位累加sum sum*10 root.Val。每深入一层把已累加的值左移一位乘 10再拼上当前节点数字相当于把路径上的数字按位拼接而无需维护字符串。用指针传递累计结果res以*int传入递归避免每层递归都要接收返回值再逐层回传符合 Go 中处理全局累计量的惯用写法。完整代码实现仓库中该题的解法位于 129. Sum Root to Leaf Numbers.go完整代码与逐行解析如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *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) }逐行解析sumNumbers是对外入口初始化结果变量res : 0以初始累加值0启动递归返回最终结果。入口函数不处理空树判断空树的情况交给dfs的root nil分支自然消化直接返回res保持 0。dfs(root, sum, res)的三层递归逻辑if root nil { return }空节点直接返回这是递归终止条件同时天然覆盖了空树与单子树某侧为空的情形sum sum*10 root.Val当前层的累加值在父层累加值基础上左移拼接。由于sum是值传递参数每个分支拿到的是独立的副本左右子树之间不会互相污染——这正是用参数而非全局变量传递路径状态的好处if root.Left nil root.Right nil { *res sum; return }判断叶子节点无左右孩子把当前路径数字计入总和并立即返回不再向下递归否则继续递归左右子树。从源码结构看遍历顺序是先处理当前节点累加、再递归左、再递归右是标准的前序遍历框架。复杂度分析时间复杂度O(n)。每个节点恰好被访问一次每次访问只做常数次算术与比较操作其中 n 为树中节点数。空间复杂度O(h)。递归调用栈的最大深度等于树高 h对平衡树为 O(log n)最坏退化为链状树时为 O(n)。此外没有使用任何额外数据结构。测试用例与验证方式该题的测试文件为 129. Sum Root to Leaf Numbers_test.go采用本仓库统一的question129参数化测试风格覆盖了三个用例输入层序数组构建树结构期望输出覆盖点[]int{}空树根为 nil0边界空输入不触发 panic结果保持 0[]int{1, 2, 3}完全二叉树示例 125两条深度为 2 的路径累加[]int{4, 9, 0, 5, 1}示例 2 的树1026不同深度路径495、491、40混合累加且含 0 值节点func Test_Problem129(t *testing.T) { qs : []question129{ { para129{[]int{}}, ans129{0}, }, { para129{[]int{1, 2, 3}}, ans129{25}, }, { para129{[]int{4, 9, 0, 5, 1}}, ans129{1026}, }, } fmt.Printf(------------------------Leetcode Problem 129------------------------\n) for _, q : range qs { _, p : q.ans129, q.para129 fmt.Printf(【input】:%v , p) root : structures.Ints2TreeNode(p.one) fmt.Printf(【output】:%v \n, sumNumbers(root)) } fmt.Printf(\n\n\n) }测试中构建树依赖 structures/TreeNode.go 中的Ints2TreeNode它把 LeetCode 层序数组通过队列做广度优先展开还原为*TreeNode空数组返回nil值为NULL-1 63哨兵的位置不创建节点。因此[4,9,0,5,1]会被还原为题面示例 2 中9 有左右孩子 5、10 无孩子的形态——这也解释了为何路径4-0会在 0 处被判定为叶子并计入40。本地运行验证仓库根目录提供了 gotest.sh其内容为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...可一次跑完全部题解测试并生成覆盖率文件只验证本题时也可以单独执行go test ./leetcode/0129.Sum-Root-to-Leaf-Numbers/模块信息见 go.modgo 1.19并通过replace指令将structures指向本地./structures目录。与 LeetCode 257 的对照同一骨架的两种路径处理题解文档特别提到本题是 257 的变体两者的对照能直观体现遍历骨架不变、只换路径处理逻辑这一复用思想维度257 二叉树路径129 根到叶数字之和路径状态字符串拼接strconv.Itoa(root.Val)-subpath整数位移拼接sum*10 root.Val叶子节点动作收集完整路径字符串将当前数字累加进res返回类型[]string逐层递归回传切片int指针累计无需回传递归传参每层接收子树返回的[]string每层只传标量sum与*int257 的实现257. Binary Tree Paths.go采用自底向上拼接先递归取左、右子树的路径列表再在父层把当前节点值拼到每条子路径前缀而 129 的解法选择自顶向下累加参数里只带一个int内存与心智负担都更小。两者都是合法思路本题用自顶向下累加更贴合边遍历边计算的场景。小结本题的核心模式是前序遍历 递归参数携带累加状态 叶子节点统一结算sum*10 val完成数字的十进制拼接*int指针完成跨层累计root nil分支统一兜底空树与单子树边界。仓库中 leetcode/0129.Sum-Root-to-Leaf-Numbers 目录下的解法、测试与中文 README 三者一一对应配合 structures/TreeNode.go 的Ints2TreeNode即可完成层序数组 → 树 → 求和的完整验证闭环。掌握该模式后凡是沿根到叶路径聚合信息的题目路径求和、路径计数、路径拼接等都可以套用同样的 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），仅供参考 LeetCode-Go 实战：LeetCode 129 根到叶数字之和的递归累加解法
LeetCode-Go 实战LeetCode 129 根到叶数字之和的递归累加解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中 129. Sum Root to Leaf Numbers 题解文档 展开完整讲解根到叶路径数字求和这道经典二叉树题目的题意、两个标准示例、前序遍历累加的解题思路与完整 Go 实现并结合仓库源码分析sum sum*10 root.Val这一核心技巧的实现细节、测试用例的覆盖方式与本地运行验证方法。读完后你能掌握在递归遍历中携带累加状态、于叶子节点统一结算这一通用模式并能直接复用其解决路径拼接类问题如 LeetCode 257 二叉树路径。题目描述给定一个二叉树它的每个结点都存放一个0-9的数字每条从根到叶子节点的路径都代表一个数字。例如从根到叶子节点路径1-2-3代表数字123。计算从根到叶子节点生成的所有数字之和。注意叶子节点是指没有子节点的节点。示例 1Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: 路径 1-2 表示数字 12 路径 1-3 表示数字 13 因此 sum 12 13 25示例 2Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026 Explanation: 路径 4-9-5 表示数字 495 路径 4-9-1 表示数字 491 路径 4-0 表示数字 40 因此 sum 495 491 40 1026解题思路前序遍历 路径累加题解文档给出的核心思路是运用前序遍历的思想从根节点出发一路累加直到叶子节点时汇总一次最后返回所有叶子节点汇总的总和。文档同时指出本题是 LeetCode 257 二叉树路径 的变体257 要求输出每条从根到叶的路径而本题把每条路径上的数字拼接成一个十进制整数后累加。两者的遍历骨架完全一致区别只在于路径上的处理动作不同——257 是拼接字符串129 是做十进制位移累加。实现上有两个关键设计十进制移位累加sum sum*10 root.Val。每深入一层把已累加的值左移一位乘 10再拼上当前节点数字相当于把路径上的数字按位拼接而无需维护字符串。用指针传递累计结果res以*int传入递归避免每层递归都要接收返回值再逐层回传符合 Go 中处理全局累计量的惯用写法。完整代码实现仓库中该题的解法位于 129. Sum Root to Leaf Numbers.go完整代码与逐行解析如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *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) }逐行解析sumNumbers是对外入口初始化结果变量res : 0以初始累加值0启动递归返回最终结果。入口函数不处理空树判断空树的情况交给dfs的root nil分支自然消化直接返回res保持 0。dfs(root, sum, res)的三层递归逻辑if root nil { return }空节点直接返回这是递归终止条件同时天然覆盖了空树与单子树某侧为空的情形sum sum*10 root.Val当前层的累加值在父层累加值基础上左移拼接。由于sum是值传递参数每个分支拿到的是独立的副本左右子树之间不会互相污染——这正是用参数而非全局变量传递路径状态的好处if root.Left nil root.Right nil { *res sum; return }判断叶子节点无左右孩子把当前路径数字计入总和并立即返回不再向下递归否则继续递归左右子树。从源码结构看遍历顺序是先处理当前节点累加、再递归左、再递归右是标准的前序遍历框架。复杂度分析时间复杂度O(n)。每个节点恰好被访问一次每次访问只做常数次算术与比较操作其中 n 为树中节点数。空间复杂度O(h)。递归调用栈的最大深度等于树高 h对平衡树为 O(log n)最坏退化为链状树时为 O(n)。此外没有使用任何额外数据结构。测试用例与验证方式该题的测试文件为 129. Sum Root to Leaf Numbers_test.go采用本仓库统一的question129参数化测试风格覆盖了三个用例输入层序数组构建树结构期望输出覆盖点[]int{}空树根为 nil0边界空输入不触发 panic结果保持 0[]int{1, 2, 3}完全二叉树示例 125两条深度为 2 的路径累加[]int{4, 9, 0, 5, 1}示例 2 的树1026不同深度路径495、491、40混合累加且含 0 值节点func Test_Problem129(t *testing.T) { qs : []question129{ { para129{[]int{}}, ans129{0}, }, { para129{[]int{1, 2, 3}}, ans129{25}, }, { para129{[]int{4, 9, 0, 5, 1}}, ans129{1026}, }, } fmt.Printf(------------------------Leetcode Problem 129------------------------\n) for _, q : range qs { _, p : q.ans129, q.para129 fmt.Printf(【input】:%v , p) root : structures.Ints2TreeNode(p.one) fmt.Printf(【output】:%v \n, sumNumbers(root)) } fmt.Printf(\n\n\n) }测试中构建树依赖 structures/TreeNode.go 中的Ints2TreeNode它把 LeetCode 层序数组通过队列做广度优先展开还原为*TreeNode空数组返回nil值为NULL-1 63哨兵的位置不创建节点。因此[4,9,0,5,1]会被还原为题面示例 2 中9 有左右孩子 5、10 无孩子的形态——这也解释了为何路径4-0会在 0 处被判定为叶子并计入40。本地运行验证仓库根目录提供了 gotest.sh其内容为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...可一次跑完全部题解测试并生成覆盖率文件只验证本题时也可以单独执行go test ./leetcode/0129.Sum-Root-to-Leaf-Numbers/模块信息见 go.modgo 1.19并通过replace指令将structures指向本地./structures目录。与 LeetCode 257 的对照同一骨架的两种路径处理题解文档特别提到本题是 257 的变体两者的对照能直观体现遍历骨架不变、只换路径处理逻辑这一复用思想维度257 二叉树路径129 根到叶数字之和路径状态字符串拼接strconv.Itoa(root.Val)-subpath整数位移拼接sum*10 root.Val叶子节点动作收集完整路径字符串将当前数字累加进res返回类型[]string逐层递归回传切片int指针累计无需回传递归传参每层接收子树返回的[]string每层只传标量sum与*int257 的实现257. Binary Tree Paths.go采用自底向上拼接先递归取左、右子树的路径列表再在父层把当前节点值拼到每条子路径前缀而 129 的解法选择自顶向下累加参数里只带一个int内存与心智负担都更小。两者都是合法思路本题用自顶向下累加更贴合边遍历边计算的场景。小结本题的核心模式是前序遍历 递归参数携带累加状态 叶子节点统一结算sum*10 val完成数字的十进制拼接*int指针完成跨层累计root nil分支统一兜底空树与单子树边界。仓库中 leetcode/0129.Sum-Root-to-Leaf-Numbers 目录下的解法、测试与中文 README 三者一一对应配合 structures/TreeNode.go 的Ints2TreeNode即可完成层序数组 → 树 → 求和的完整验证闭环。掌握该模式后凡是沿根到叶路径聚合信息的题目路径求和、路径计数、路径拼接等都可以套用同样的 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），仅供参考