LeetCode 129 求根到叶节点数字之和Sum Root to Leaf Numbers四种遍历方案与多语言实现剖析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 129「求根到叶节点数字之和」展开讲解如何把二叉树上每条根到叶子的路径拼接为一个十进制整数并求和。文章完整覆盖递归 DFS、BFS 层序、迭代 DFS 与 Morris 遍历四种解法并结合当前仓库 leetcode 中 C、C、Java、Go、JavaScript、Kotlin 等多语言源码进行交叉印证。读完本文你将掌握路径数字累加的标准写法num * 10 val、叶子节点的判定时机、显式栈与 O(1) 空间的 Morris 技巧以及多语言实现之间的差异与取舍。1. 问题定义与核心思路题目要求给定一棵二叉树每个节点存放 09 的数字每条从根到叶子的路径按顺序拼接后得到一个整数例如路径1 → 2 → 3对应数字123返回所有根到叶子路径数字的总和。1.1 问题本质每条根到叶路径是一个数字序列拼接规则等价于十进制按位累加num num * 10 cur.val。只有叶子节点左右孩子均为空才构成一条完整路径内部节点不能提前结算。遍历顺序没有严格要求前序、层序、中序均可关键是在携带路径状态的前提下访问所有叶子。1.2 仓库中的题目原型本仓库按题号存放实现与本文对应的是0129号题目例如C 语言实现C 语言实现Java 语言实现Go 语言实现JavaScript 语言实现Kotlin 语言实现后文将在讲解完四类算法后逐一对照这些源码指出仓库实现与本文伪代码之间的对应关系。2. 前置知识在动手之前建议先熟悉以下三个基础能力二叉树遍历Binary Tree Traversal理解如何通过父节点与孩子节点的引用关系在树中移动。深度优先搜索DFS递归地沿根到叶探索路径同时维护遍历状态。路径追踪Path Tracking沿路径累加数值并正确识别叶子节点没有孩子的节点。这些能力也是仓库中大量树类题目的通用前提例如 binary-tree-inorder-traversal.md、binary-tree-preorder-traversal.md 等文章都建立在相同的基础上。3. 方案一递归深度优先搜索DFS3.1 直觉树中每条根到叶路径都代表一个数字数字从根到叶按位拼接。沿树下行时通过「将已累加值乘以 10 再加上当前节点值」来构造数字到达叶子时就得到了一条完整的路径数字可以累加到总和。DFS 天然沿根到叶的路径推进是该问题最直接的解法。3.2 算法步骤定义递归函数dfs(cur, num)参数为当前节点与已累加的数字若当前节点为空返回0空子树的基础情况更新累加数字num num * 10 cur.val若当前节点是叶子无左右孩子返回该累加数字否则递归处理左右孩子返回两者结果之和从根节点、初始数字0开始调用dfs。3.3 多语言实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def sumNumbers(self, root: TreeNode) - int: def dfs(cur, num): if not cur: return 0 num num * 10 cur.val if not cur.left and not cur.right: return num return dfs(cur.left, num) dfs(cur.right, num) return dfs(root, 0)public class Solution { public int sumNumbers(TreeNode root) { return dfs(root, 0); } private int dfs(TreeNode cur, int num) { if (cur null) return 0; num num * 10 cur.val; if (cur.left null cur.right null) return num; return dfs(cur.left, num) dfs(cur.right, num); } }class Solution { public: int sumNumbers(TreeNode* root) { return dfs(root, 0); } private: int dfs(TreeNode* cur, int num) { if (!cur) return 0; num num * 10 cur-val; if (!cur-left !cur-right) return num; return dfs(cur-left, num) dfs(cur-right, num); } };class Solution { sumNumbers(root) { const dfs (cur, num) { if (!cur) return 0; num num * 10 cur.val; if (!cur.left !cur.right) return num; return dfs(cur.left, num) dfs(cur.right, num); }; return dfs(root, 0); } }func sumNumbers(root *TreeNode) int { var dfs func(cur *TreeNode, num int) int dfs func(cur *TreeNode, num int) int { if cur nil { return 0 } num num*10 cur.Val if cur.Left nil cur.Right nil { return num } return dfs(cur.Left, num) dfs(cur.Right, num) } return dfs(root, 0) }同一逻辑在仓库的 C 实现 中体现得尤为直观dfs递归函数接收当前节点与累加值acc遇到叶子返回acc*10 r-val非叶子则分别递归左右子树并把两者求和入口sumNumbers直接调用dfs(root, 0)。Kotlin 版本kotlin/0129-sum-root-to-leaf-numbers.kt则把累加过程拆为current * 10 root.value并写入外部变量res语义等价。C#、Swift、Rust 的实现与本段一致可参考 articles/sum-root-to-leaf-numbers.md 的完整 tabs 代码块。3.4 复杂度分析时间复杂度$O(n)$其中 $n$ 为节点总数每个节点恰好访问一次。空间复杂度$O(h)$$h$ 为树高来自递归调用栈的深度。4. 方案二广度优先搜索BFS / 层序4.1 直觉DFS 是「先深入再回溯」BFS 则是借助队列逐层推进。队列中的每个元素同时保存节点与到达该节点时累计的数字。出队时若遇到叶子就把累计数字加入总和。BFS 保证访问全部节点同时每个路径的数值彼此独立地随节点一起传递。4.2 算法步骤初始化结果变量res 0队列初始放入(root, 0)当队列非空时循环出队一个节点及其累计数字更新数字num num * 10 cur.val若该节点是叶子把num累加到res否则将每个非空孩子与当前累计数字一起入队返回res。4.3 多语言实现from collections import deque class Solution: def sumNumbers(self, root: TreeNode) - int: res 0 q deque([(root, 0)]) while q: cur, num q.popleft() num num * 10 cur.val if not cur.left and not cur.right: res num continue if cur.left: q.append((cur.left, num)) if cur.right: q.append((cur.right, num)) return resclass Solution { public: int sumNumbers(TreeNode* root) { int res 0; queuepairTreeNode*, int q; q.push({root, 0}); while (!q.empty()) { auto [cur, num] q.front(); q.pop(); num num * 10 cur-val; if (!cur-left !cur-right) { res num; continue; } if (cur-left) q.push({cur-left, num}); if (cur-right) q.push({cur-right, num}); } return res; } };public class Solution { public int sumNumbers(TreeNode root) { int res 0; QueuePairTreeNode, Integer q new LinkedList(); q.offer(new Pair(root, 0)); while (!q.isEmpty()) { PairTreeNode, Integer p q.poll(); TreeNode cur p.getKey(); int num p.getValue() * 10 cur.val; if (cur.left null cur.right null) { res num; continue; } if (cur.left ! null) q.offer(new Pair(cur.left, num)); if (cur.right ! null) q.offer(new Pair(cur.right, num)); } return res; } }func sumNumbers(root *TreeNode) int { res : 0 type pair struct { node *TreeNode num int } q : []pair{{root, 0}} for len(q) 0 { cur : q[0] q q[1:] newNum : cur.num*10 cur.node.Val if cur.node.Left nil cur.node.Right nil { res newNum continue } if cur.node.Left ! nil { q append(q, pair{cur.node.Left, newNum}) } if cur.node.Right ! nil { q append(q, pair{cur.node.Right, newNum}) } } return res }仓库的 C 迭代实现 采用「显式栈 前序」而非队列栈元素同样保存(node, num)二元组弹出后若为叶子则累加否则把左右孩子以num * 10 child-val的形式压栈。它与 BFS 的关键区别在于访问顺序深度优先 vs 层序但「节点与累计数字绑定传递」这一思想完全一致。4.4 复杂度分析时间复杂度$O(n)$。空间复杂度$O(n)$最坏情况下如完全二叉树队列需要容纳一整层的节点。5. 方案三迭代 DFS显式栈5.1 直觉递归 DFS 使用系统调用栈极深的树可能触发栈溢出。方案三用显式栈模拟递归过程核心技巧是「一路向左把右孩子连同当时的累计数字压栈留待后续处理」。栈中的每个条目都记录了到达该点时的累计数字从而保证后续能正确地继续构造路径值。5.2 算法步骤初始化res 0、空栈当前节点为root数字num 0当cur非空或栈非空时循环若cur非空更新数字num num * 10 cur.val若是叶子把num累加到res将(cur.right, num)压栈走向左孩子cur cur.left否则出栈得到下一节点及其累计数字返回res。5.3 多语言实现class Solution: def sumNumbers(self, root: Optional[TreeNode]) - int: res 0 stack [] cur, num root, 0 while cur or stack: if cur: num num * 10 cur.val if not cur.left and not cur.right: res num stack.append((cur.right, num)) cur cur.left else: cur, num stack.pop() return respublic class Solution { public int sumNumbers(TreeNode root) { int res 0, num 0; StackPairTreeNode, Integer stack new Stack(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { if (cur ! null) { num num * 10 cur.val; if (cur.left null cur.right null) res num; stack.push(new Pair(cur.right, num)); cur cur.left; } else { PairTreeNode, Integer p stack.pop(); cur p.getKey(); num p.getValue(); } } return res; } }class Solution { public: int sumNumbers(TreeNode* root) { int res 0; stackpairTreeNode*, int st; TreeNode* cur root; int num 0; while (cur || !st.empty()) { if (cur) { num num * 10 cur-val; if (!cur-left !cur-right) res num; st.push({cur-right, num}); cur cur-left; } else { cur st.top().first; num st.top().second; st.pop(); } } return res; } };class Solution { sumNumbers(root) { let res 0, num 0; let stack []; let cur root; while (cur || stack.length) { if (cur) { num num * 10 cur.val; if (!cur.left !cur.right) res num; stack.push([cur.right, num]); cur cur.left; } else { [cur, num] stack.pop(); } } return res; } }func sumNumbers(root *TreeNode) int { res, num : 0, 0 type item struct { node *TreeNode num int } stack : []item{} cur : root for cur ! nil || len(stack) 0 { if cur ! nil { num num*10 cur.Val if cur.Left nil cur.Right nil { res num } stack append(stack, item{cur.Right, num}) cur cur.Left } else { top : stack[len(stack)-1] stack stack[:len(stack)-1] cur, num top.node, top.num } } return res }5.4 复杂度分析时间复杂度$O(n)$。空间复杂度$O(h)$显式栈在最坏情况下退化为链表的树也只会保存 $O(h)$ 个条目与递归版本的调用栈深度同级但避免了系统栈溢出的风险。6. 方案四Morris 遍历O(1) 额外空间6.1 直觉Morris 遍历通过临时修改树结构在前驱节点与后继节点之间建立临时指针实现无栈、无递归的遍历从而把额外空间降到 $O(1)$。本题的难点在于沿左子树下行时累计了若干位数字当通过临时链接「回溯」到某个节点时需要把这些多算的位数撤销。解法是记录从当前节点到达其前驱所走的步数steps回溯时用num / 10^steps去掉左子树贡献的位数。6.2 算法步骤预计算 10 的幂power[i] 10^i供快速除法使用当cur非空时循环若cur无左孩子累加当前位num num * 10 cur.val若cur无右孩子即为叶子把num加入res移动到右孩子cur cur.right否则有左孩子找到左子树的中序前驱prev左子树中最右的节点同时统计步数steps若prev.right为空建立临时链接prev.right cur累加当前位后走向左孩子若prev.right指向cur说明正在回溯删除临时链接若prev是叶子则把num加入res用num / power[steps]撤销左子树位数走向右孩子返回res。6.3 多语言实现class Solution: def sumNumbers(self, root: Optional[TreeNode]) - int: res 0 cur root num 0 power [1] * 10 for i in range(1, 10): power[i] power[i - 1] * 10 while cur: if not cur.left: num num * 10 cur.val if not cur.right: res num cur cur.right else: prev cur.left steps 1 while prev.right and prev.right ! cur: prev prev.right steps 1 if not prev.right: prev.right cur num num * 10 cur.val cur cur.left else: prev.right None if not prev.left: res num num // power[steps] cur cur.right return respublic class Solution { public int sumNumbers(TreeNode root) { int res 0, num 0; int[] power new int[10]; power[0] 1; for (int i 1; i 10; i) { power[i] power[i - 1] * 10; } TreeNode cur root; while (cur ! null) { if (cur.left null) { num num * 10 cur.val; if (cur.right null) res num; cur cur.right; } else { TreeNode prev cur.left; int steps 1; while (prev.right ! null prev.right ! cur) { prev prev.right; steps; } if (prev.right null) { prev.right cur; num num * 10 cur.val; cur cur.left; } else { prev.right null; if (prev.left null) res num; num / power[steps]; cur cur.right; } } } return res; } }class Solution { public: int sumNumbers(TreeNode* root) { int res 0, num 0; int power[10] {1}; for (int i 1; i 10; i) { power[i] power[i - 1] * 10; } TreeNode* cur root; while (cur) { if (!cur-left) { num num * 10 cur-val; if (!cur-right) res num; cur cur-right; } else { TreeNode* prev cur-left; int steps 1; while (prev-right prev-right ! cur) { prev prev-right; steps; } if (!prev-right) { prev-right cur; num num * 10 cur-val; cur cur-left; } else { prev-right nullptr; if (!prev-left) res num; num / power[steps]; cur cur-right; } } } return res; } };class Solution { sumNumbers(root) { let res 0, num 0; let power Array(10).fill(1); for (let i 1; i 10; i) { power[i] power[i - 1] * 10; } let cur root; while (cur) { if (!cur.left) { num num * 10 cur.val; if (!cur.right) res num; cur cur.right; } else { let prev cur.left, steps 1; while (prev.right prev.right ! cur) { prev prev.right; steps; } if (!prev.right) { prev.right cur; num num * 10 cur.val; cur cur.left; } else { prev.right null; if (!prev.left) res num; num Math.floor(num / power[steps]); cur cur.right; } } } return res; } }func sumNumbers(root *TreeNode) int { res, num : 0, 0 power : make([]int, 10) power[0] 1 for i : 1; i 10; i { power[i] power[i-1] * 10 } cur : root for cur ! nil { if cur.Left nil { num num*10 cur.Val if cur.Right nil { res num } cur cur.Right } else { prev : cur.Left steps : 1 for prev.Right ! nil prev.Right ! cur { prev prev.Right steps } if prev.Right nil { prev.Right cur num num*10 cur.Val cur cur.Left } else { prev.Right nil if prev.Left nil { res num } num / power[steps] cur cur.Right } } } return res }6.4 复杂度分析时间复杂度$O(n)$每个节点最多被「建立链接 / 撤销链接」各处理常数次。空间复杂度$O(1)$ 额外空间不考虑输入树本身是四种方案中唯一不依赖栈或队列的实现。注意Morris 遍历会临时修改树结构建立并随后删除前驱到当前节点的右指针。若题目或环境要求遍历期间树不可变则该方案不适用它最适合空间受限且允许临时改动的场景。这也是为什么仓库中的常规实现如 cpp/0129-sum-root-to-leaf-numbers.cpp、java/0129-sum-root-to-leaf-numbers.java优先采用栈/递归方案以保证树结构不被触碰。7. 仓库源码对照多语言实现的思路变体除了文章核心讲解的四类算法仓库内0129题目的实现还提供了若干值得学习的思路变体7.1 C纯递归边界合并精简c/0129-sum-root-to-leaf-numbers.c 将「空节点」与「叶子」两种情况分开处理空节点直接返回已累加值acc叶子返回acc*10 r-val单孩子节点则只递归存在的分支。这种写法通过提前剪枝减少了递归调用次数且代码注释明确标注了Space: O(1) / Time: O(n)此处指忽略递归栈的辅助空间。7.2 Java数值累加 vs 字符串拼接java/0129-sum-root-to-leaf-numbers.java 同时给出了两种解法数值累加版currentPath currentPath * 10 node.val边遍历边构造整数空间 $O(h)$字符串拼接版用字符串currentPath node.val记录路径抵达叶子后Integer.parseInt(curr)转整数求和。空间升至 $O(V)$需保存所有路径字符串但逻辑更贴近「拼接数字」的字面语义适合作为教学对照。7.3 JavaScript字符串拼接 一元加号javascript/0129-sum-root-to-leaf-numbers.js 同样采用字符串路径在叶子处用一元加号num把拼接结果转成数字累加配合node.left dfs(...)的短路写法非常简洁注释标注为pre-order-traversal / Time O(n) / Space O(n)。7.4 Go路径收集后统一求和go/0129-sum-root-to-leaf-numbers.go 先用 DFS 把所有叶子路径数字收集到切片res再用辅助函数sum(...)一次性求和。这种「先收集、后聚合」的写法把「如何算」与「何时算」解耦便于扩展为「返回所有路径数字列表」的需求。7.5 Kotlin扩展属性简化取值kotlin/0129-sum-root-to-leaf-numbers.kt 定义了val TreeNode.value get() this.\val扩展属性把val关键字带来的转义噪声封装起来主逻辑current * 10 root.value 因而更加清爽展示了语言特性对可读性的优化。以上源码共同印证了核心结论无论采用何种语言或遍历方式num num * 10 node.val与「叶子才结算」这两条规则保持不变。8. 常见陷阱Common Pitfalls8.1 把内部节点的值也加入总和最常见的错误是在每个节点处都把累计数字累加到结果而题目要求的是「根到叶」路径数字因此必须同时满足left null right null才可结算。若在内部节点提前累加会统计出大量半截路径结果必然偏大且错误。8.2 数字累加公式写错构造路径数字时必须先乘 10 再加当前位num num * 10 node.val。常见错误是先加后乘或漏掉乘法导致结果退化为个位数或拼接错误。牢记树每下降一层数字就多出一个十进制位。8.3 不处理单节点树当树只有根节点、没有任何孩子时根节点本身就是叶子合法路径数字就是root.val。有些实现会在此情况返回 0 或漏判务必保证基础情况能正确返回根值作为完整数字。对照仓库 c/0129-sum-root-to-leaf-numbers.c 的叶子分支可看到该处理的正确写法。9. 四种方案对比与总结方案遍历方式时间空间适用场景递归 DFS深度优先前序$O(n)$$O(h)$代码最简洁默认首选BFS 层序广度优先$O(n)$$O(n)$希望按层理解、避免递归迭代 DFS深度优先显式栈$O(n)$$O(h)$树很深规避系统栈溢出Morris 遍历中序变体临时改树$O(n)$$O(1)$严格空间受限且允许临时修改树其中 $n$ 为节点数$h$ 为树高。实际面试与刷题中递归 DFS 是默认首选它最直观、最不易出错当树深可能很大时切换到迭代 DFS只有在空间被严格限制的极端场景下才考虑Morris 遍历同时需要确认允许临时改动树结构。完整的多语言 tabs 代码含 C#、Swift、Rust 版本可在 articles/sum-root-to-leaf-numbers.md 中查看仓库内0129号源码文件c、cpp、java、go、javascript、kotlin则提供了可直接运行的参考实现。掌握本题的「按位累加 叶子结算」范式后你还可以顺带攻克 sum-root-to-leaf-numbers 的进阶变形例如在路径中加入前缀 0、限制位数或要求返回路径列表等变体问题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考