企业官网建设流程全解析

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. 问题定义与核心思路

题目要求：给定一棵二叉树，每个节点存放 0～9 的数字，每条从根到叶子的路径按顺序拼接后得到一个整数（例如路径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. 方案一：递归深度优先搜索（DFS）

3.1 直觉

树中每条根到叶路径都代表一个数字，数字从根到叶按位拼接。沿树下行时，通过「将已累加值乘以 10 再加上当前节点值」来构造数字；到达叶子时，就得到了一条完整的路径数字，可以累加到总和。DFS 天然沿根到叶的路径推进，是该问题最直接的解法。

3.2 算法步骤

1. 定义递归函数dfs(cur, num)，参数为当前节点与已累加的数字；
2. 若当前节点为空，返回0（空子树的基础情况）；
3. 更新累加数字：num = num * 10 + cur.val；
4. 若当前节点是叶子（无左右孩子），返回该累加数字；
5. 否则递归处理左右孩子，返回两者结果之和；
6. 从根节点、初始数字0开始调用dfs。

3.3 多语言实现

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # 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 算法步骤

1. 初始化结果变量res = 0，队列初始放入(root, 0)；
2. 当队列非空时循环：
   • 出队一个节点及其累计数字；
   • 更新数字：num = num * 10 + cur.val；
   • 若该节点是叶子，把num累加到res；
   • 否则，将每个非空孩子与当前累计数字一起入队；
3. 返回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 res

class Solution { public: int sumNumbers(TreeNode* root) { int res = 0; queue<pair<TreeNode*, 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; Queue<Pair<TreeNode, Integer>> q = new LinkedList<>(); q.offer(new Pair<>(root, 0)); while (!q.isEmpty()) { Pair<TreeNode, 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 算法步骤

1. 初始化res = 0、空栈，当前节点为root，数字num = 0；
2. 当cur非空或栈非空时循环：
   • 若cur非空：
     • 更新数字：num = num * 10 + cur.val；
     • 若是叶子，把num累加到res；
     • 将(cur.right, num)压栈；
     • 走向左孩子cur = cur.left；
   • 否则：出栈得到下一节点及其累计数字；
3. 返回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 res

public class Solution { public int sumNumbers(TreeNode root) { int res = 0, num = 0; Stack<Pair<TreeNode, 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 { Pair<TreeNode, Integer> p = stack.pop(); cur = p.getKey(); num = p.getValue(); } } return res; } }

class Solution { public: int sumNumbers(TreeNode* root) { int res = 0; stack<pair<TreeNode*, 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 算法步骤

1. 预计算 10 的幂power[i] = 10^i，供快速除法使用；
2. 当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]撤销左子树位数；走向右孩子；
3. 返回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 res

public 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 Pitfalls）

8.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. 四种方案对比与总结

其中 $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