LeetCode LCR 049. 求根节点到叶节点数字之和
题目描述
题意分析
每个节点保存一位十进制数字，一条从根到叶子的路径按顺序拼成一个整数，要求这些整数的总和。只有到达叶子才形成完整数字，内部节点上的路径前缀不能单独计入答案。
LCR 049 注明与主站 129 同题，主站题面 明确保证最终答案在 32 位整数范围内，代码据此使用
int。仅有“深度不超过 10”这一条件，不能单独保证十位数不溢出。
解法：DFS 累积路径数字
核心思路
[!blue]
沿根到当前节点的路径逐位拼接数字。如果到父节点的前缀是
presum，加入当前一位后就是presum*10+node.val：旧数位整体向左移一位，当前数字放在个位。定义
dfs(node, presum)返回：在已知父节点路径前缀为presum的情况下，当前子树中所有叶子最终贡献的数字之和。进入当前节点后先更新前缀；若它是叶子，直接返回完整数字；否则将新前缀传给左右孩子，并把两个返回值相加。每条根到叶路径恰好在自己的叶子处结算一次，左右子树的叶子互不重叠，因此相加不会遗漏或重复。前缀通过整数参数按值传递，两个孩子各自更新自己的副本，不需要手动撤销，也不会相互污染。
解题步骤
- 从
dfs(root, 0)开始，根之前没有数位，所以初始前缀为 0。- 空节点返回 0，表示这一侧没有叶子路径贡献。
- 非空节点计算包含当前位的新前缀。
- 左右孩子都为空时返回新前缀；否则返回左右递归结果之和。
只有一个孩子的节点仍需继续递归，空的一侧只贡献 0；单节点树则直接返回根值。所有数位非负，每条路径前缀不超过完整路径值，各子树贡献也不超过最终总和，所以在上述答案范围保证下，中间运算同样安全。
代码实现
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$ 为树高；无需另外保存路径列表。
关键点总结
[!green]
- 向下传递的是当前路径的数字前缀，向上返回的是子树全部叶子的总贡献。
- 只在左右孩子都为空的叶子处结算，内部前缀不再额外相加。
- 数位按十进制拼接，零也要照常占据一位，使用乘 10 再加值即可。
易错点总结
[!yellow]
- 叶子要求左右孩子都为空，只有一侧为空时不能提前结算。
- 前缀更新为 previous*10+当前值，空节点贡献 0。
- 把前缀按值传给两个孩子，避免一个分支污染另一个分支的路径数字。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 112. 路径总和 | 简单 | 同样沿根到叶路径累积状态，本题每深入一层乘10再加数字，原题直接累加节点值。 |
| 1022. 从根到叶的二进制数之和 | 简单 | 同样把根路径当作一个数，本题十进制，原题二进制。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！