LeetCode LCR 049. 求根节点到叶节点数字之和
目录
题目描述
题意分析
题目目标：树上每个节点的值都是 0 到 9 的一位数字，从根到某个叶子的一条路径按顺序拼起来就是一个整数，要求把所有"根到叶"路径对应的整数全部加起来返回。
核心约束：只有以叶子结尾的路径才算数——中途停下的前缀不产生贡献，这决定了结算时机必须精确落在叶子上；同时数字是按十进制从高位往低位拼接的，说明沿路径下行时新的一位应该以"旧值乘十再加当前位"的方式并入。
边界处理：树可能为空，答案为 0；只有一个节点时它既是根也是叶，答案就是它本身；只有一个孩子的节点不是叶子，绝不能提前结算；题目保证深度不超过 10，因此拼出的数字不会超过十位，用 32 位整型累加是安全的。
实现取舍：每条路径的数字都由它的前缀唯一决定，兄弟分支之间互不干扰，所以只要在下行时把"当前前缀值"顺着传下去，就不必真的存下任何一条路径。
解法：深度优先搜索
核心思路
暴力做法是先把所有根到叶的路径完整枚举并存进列表，再逐条把数字拼出来求和。逻辑没错，但每条路径都要单独重建一次数字，路径之间共享的前缀被反复计算，还额外花掉 $O(n \cdot h)$ 的空间去存路径。
观察到共享前缀这件事可以被利用：从根走到某个节点时，路径前缀对应的数字是完全确定的，而且它对左右两个子树同样有效。既然如此，就把这个前缀值作为参数一路带下去，走一步更新一次，谁也不用回头重算。
由此定义递归的语义：dfs(node, presum)表示"已知从根到node父亲的路径拼成的数字是presum，返回以node为起点的所有完整路径所贡献的数字之和"。这个返回值定义把"局部子树的总贡献"封装了起来，父亲只需把左右两个返回值相加。
进入节点时先算出属于自己的前缀s = presum * 10 + node.val，为什么是乘十：路径每向下延伸一层，之前的所有位数就整体左移一位，新节点的数字占据个位。若node是叶子，路径到此结束，直接返回s；否则把s传给左右孩子并把两边的结果相加，空孩子返回 0 从而不产生任何贡献。
解题步骤
- 主函数直接调用
dfs(root, 0)。为什么初始前缀是 0：根之上没有任何数位，0 * 10 + root.val恰好等于根值本身，这样根就不需要任何特判。- 递归入口遇到空节点返回 0。为什么返回 0 而不是别的：0 是加法的单位元，让"只有一个孩子的节点"在求和时自动忽略缺失的那一侧，无需写额外分支。
- 进入节点后立刻计算
s = presum * 10 + root.val。为什么在最开始算：后续无论是结算还是下传都用得到它，先算一次可以避免在两个分支里重复书写，也保证左右子树拿到的前缀完全相同。- 判断
root.left == null && root.right == null时返回s。为什么两个孩子都必须为空：只有一个孩子的节点仍在路径中途，此时结算会把一个不完整的数字算进答案。- 非叶子节点返回
dfs(root.left, s) + dfs(root.right, s)。为什么这里不再加上s：s只是路径前缀，它本身不是一个完整数字，真正的贡献已经被下游的叶子结算过了。- 以
具体用例：树[4, 9, 0, 5, 1]（根 4；左孩子 9 的左右孩子是 5、1；右孩子 0 是叶子）走一遍。dfs(4, 0)算出s = 4，不是叶子，转而求两个子树。左边dfs(9, 4)算出s = 49，也不是叶子：dfs(5, 49)算出s = 495且是叶子，返回 495；dfs(1, 49)算出s = 491且是叶子，返回 491；于是左子树返回 986。右边dfs(0, 4)算出s = 40且是叶子，返回 40。根把两侧相加得986 + 40 = 1026，与手工计算495 + 491 + 40完全一致。再看一个陷阱用例，树[1, 2]（根 1 只有左孩子 2）：dfs(1, 0)得s = 1，因为右孩子为空但左孩子存在，它不是叶子，于是返回dfs(2, 1) + dfs(null, 1) = 12 + 0 = 12，正确地只算一条路径。
代码实现
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int presum) {
if (root == null) {
return 0;
}
int s = presum * 10 + root.val;
if (root.left == null && root.right == null) {
return s;
}
return dfs(root.left, s) + dfs(root.right, s);
}
}
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
func sumNumbers(root *TreeNode) int {
var dfs func(root *TreeNode, presum int) int
dfs = func(root *TreeNode, presum int) int {
if root == nil {
return 0
}
presum = presum*10 + root.Val
if root.Left == nil && root.Right == nil {
return presum
}
return dfs(root.Left, presum) + dfs(root.Right, presum)
}
return dfs(root, 0)
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：每个节点只被访问一次，访问时做的是一次乘加、一次叶子判断和至多两次递归调用，所有路径共享前缀因而没有任何重复计算。
- 空间复杂度：$O(h)$，
h为树高，最坏（链状树）为 $O(n)$。凭什么：没有存储任何路径，唯一的额外开销是递归调用栈的深度。
关键点总结
- 自顶向下传递状态、在终点结算，是"根到叶路径"类问题的统一骨架；与之相对的是自底向上返回状态，判断依据就是"信息的流动方向和答案的结算位置"。
- 十进制拼接用
presum * 10 + val表达，这个式子可以直接推广到任意进制（二进制就是乘二），遇到"路径构成数字"的变种不必重新推导。- 空节点返回加法单位元 0，是消除"只有一个孩子"这类分支的通用手法，比显式写四种孩子组合要干净得多。
- 叶子的定义是"左右孩子都为空"，任何用"其中一个为空"来判定叶子的写法都会把中途路径当成完整路径。
- 面试视角：面试官会关心你有没有意识到溢出风险。这道题因为深度上限是 10 所以
int足够，但要主动说明"如果深度不受限，就要改用更宽的类型或者按题目要求取模"；再补一句迭代写法（用栈同时压入节点和前缀值）可以避免深树爆栈，回答就完整了。
易错点总结
- 错误写法：叶子判定写成
root.left == null || root.right == null→ 树[1, 2]时根被误判为叶子，返回 1 而不是正确的 12。- 错误写法：非叶子节点也把
s加进答案，写成return s + dfs(left, s) + dfs(right, s)→ 树[1, 2]返回1 + 12 = 13，所有中间前缀都被重复计入。- 错误写法：空节点返回
presum而不是 0 → 树[1, 2]时右侧空孩子返回 1，答案变成 13；本质是把"不存在的路径"也算了一次。- 错误写法：拼接写成
presum + root.val漏掉乘十 → 树[4, 9]应得 49，实际返回 13，数位含义完全丢失。- 错误写法：用全局变量累加答案却在递归返回后忘记恢复，或干脆在叶子处
answer += s的同时又返回s→ 树[4, 9, 0]的每条路径被计入两次，答案翻倍。- 错误写法：把前缀存在成员变量里而不是当参数传 → 左子树递归结束后前缀没有回退，右子树拿到被污染的值，树
[4, 9, 0]中右孩子的前缀变成 49 而不是 4。- 错误写法：先判空再判叶子的顺序颠倒，即先访问
root.left再判root == null→ 空树输入直接空指针异常。- 错误写法：改成先收集所有路径再逐条拼数字，却在回溯时忘记弹出当前节点 → 兄弟分支的路径互相污染，树
[4, 9, 0]会拼出490这样根本不存在的数字。- 错误写法：在允许深度更大的变种里仍用
int累加 → 深度超过 10 时前缀值突破 32 位范围变成负数，答案彻底失真。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 112. 路径总和 | 简单 | 同样在叶子结算，但只需判定存在性可提前返回 |
| 113. 路径总和 II | 中等 | 要输出路径本身，必须显式维护路径并正确回溯 |
| 257. 二叉树的所有路径 | 简单 | 结果是字符串拼接，考察分隔符与回溯的配合 |
| 1022. 从根到叶的二进制数之和 | 简单 | 同一套前缀传递，进制从十换成二 |
| 988. 从叶结点开始的最小字符串 | 中等 | 路径需反向比较字典序，结算时还要做整体取最小 |
| 437. 路径总和 III | 中等 | 路径起止都不固定，需前缀和计数而非叶子结算 |