LeetCode 129. 求根节点到叶节点数字之和
目录
题目描述
题意分析
每个节点存一个一位数字，从根走到某个叶子的路径按经过顺序拼成一个十进制整数，要求返回所有这类整数的总和。注意求的是和，不是路径列表，所以不需要把路径本身保留下来。
「节点值是一位数字」这个条件直接给出了拼接的算法信号：在一位数的前提下，「在已有数字后面接一位」就等价于「乘
10再加上这一位」，于是路径数字可以自顶向下增量维护。题面还保证结果落在32位整数范围内，因此可以放心用int累加，不必考虑溢出。「叶子」的定义是左右孩子都为空的节点，只有它才对应一条完整路径。这一点是本题绝大多数错误的来源：走到中途的节点，其路径数字只是一个前缀，不能结算。
边界情形有三类：整棵树只有一个节点，此时根同时也是叶子，答案就是根的值；某个节点只有一个孩子，它不是叶子，既不能在这里结算，也不能把它的空孩子当成叶子；路径上可以出现值为
0的节点，4 → 0 → 5拼出来的是405，任何「跳过0」的处理都是错的。
解法：DFS 传递路径数值
核心思路
深度优先遍历时，用
current = prefix * 10 + node.val把当前节点拼到路径数字末尾。只有叶子节点代表一条完整路径，此时返回current；非叶子节点返回左右子树结果之和。
解题步骤
- 从根节点开始 DFS，初始路径值为
0。- 到达节点后计算
current = prefix * 10 + node.val。- 若当前节点是叶子，返回
current。- 否则将
current传给左右孩子，并把两侧结果相加。
代码实现
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode node, int prefix) {
if (node == null) {
return 0;
}
int current = prefix * 10 + node.val;
if (node.left == null && node.right == null) {
return current;
}
return dfs(node.left, current) + dfs(node.right, current);
}
}
func sumNumbers(root *TreeNode) int {
var dfs func(*TreeNode, int) int
dfs = func(node *TreeNode, prefix int) int {
if node == nil {
return 0
}
current := prefix*10 + node.Val
if node.Left == nil && node.Right == nil {
return current
}
return dfs(node.Left, current) + dfs(node.Right, current)
}
return dfs(root, 0)
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点访问一次。
- 空间复杂度：$O(h)$，
h为树高，来自递归栈。
关键点总结
- 路径数字可增量计算，无需保存完整路径。
- 只有左右孩子都为空的节点才是叶子。
- 空子树返回
0，便于直接相加左右结果。
易错点总结
- 在非叶子节点累加路径值，会把不完整路径计入答案。
- 递归孩子时必须传
current，不能继续传旧的prefix。- 叶子判断必须同时检查左右孩子，只有一个孩子的节点不是叶子。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 112. 路径总和 | 简单 | 只问存在性，找到第一条满足的路径就能短路返回，不必把整棵树走完 |
| 113. 路径总和 II | 中等 | 要求返回路径本身，前缀信息不再可压缩成一个数，必须维护可变 path、撤销并拷贝快照 |
| 257. 二叉树的所有路径 | 简单 | 前缀是字符串而非数字，拼接不可逆，因此更适合每层传一份新副本而不是共享缓冲区 |
| 404. 左叶子之和 | 简单 | 结算条件除了「是叶子」还要看它挂在父节点的哪一侧，判断必须放到父层去做 |
| 1022. 从根到叶的二进制数之和 | 简单 | 同一套增量公式把基数从 10 换成 2，可以直接用左移加或运算代替乘加 |
| LCR 049. 求根节点到叶节点数字之和 | 中等 | 与本题同题换皮，适合用来检验参数不变量与返回值语义能否脱稿说清 |
| 剑指 Offer 34. 二叉树中和为某一值的路径 | 中等 | 目标和固定且要输出全部路径，等价于 113 题，重点转移到回溯的撤销与快照上 |