求根节点到叶节点数字之和 图解题解

这道题到底在问什么

树

[4,9,0,5,1]

路径数

495 · 491 · 40

输出

495 + 491 + 40 = 1026

最优解：一步一步想明白

1. 3拼十进制就是「进位」:已有 49,再来个 5,就是 49×10+5 = 495。所以 DFS 时带着一个 cur 往下传,每进一个节点就更新它,到叶子时 cur 正好是这条路径的完整数字。
2. 4根=4, 叶子=5 / 1 / 0绿色的 5、1、0 是叶子(下面再没有孩子)。我们要找的:根 4 到每个叶子的路径,把路上数字拼成整数,再求和。一共三条路。
3. 5只有叶子才是一条路径数的终点蓝色的 4、9 是中间节点(还有孩子),只更新 cur、不结算;绿色的 5、1、0 才是叶子,走到才把这条路径拼成的数加进总和。
4. 6顺序是先走 4→9 这一片(把 495、491 两条结算掉),再走 4→0(结算 40)。cur 用「按值传参」往下带,退回上层时自动变回上层的值,不用手动撤销。
5. 7cur = 0*10 + 4 = 4从根 4 出发,cur 从 0 更新成 0×10+4 = 4。4 有孩子,不是叶子,带着 cur=4 继续往下探它的左孩子。
6. 8cur = 4*10 + 9 = 49进入 9,cur 更新成 4×10+9 = 49。4 已经在路径上(变成路径节点)。9 还有孩子,带着 cur=49 继续探它的左孩子。
7. 99 有孩子 → 不是叶子,继续下探9 有孩子(5 和 1),不是叶子,所以现在不结算、cur 也不动,带着 cur=49 先往下探它的左孩子 5。
8. 10cur = 49*10 + 5 = 495进入 5,cur 更新成 49×10+5 = 495。先别急——得问一句:5 是叶子吗?
9. 115 左右都空 → 是叶子!5 左右都没孩子 → 是叶子,这条路径 4→9→5 拼出的数 495 走到头了,该加进总和。
10. 12总和 = 0 + 495 = 495把 495 加进总和,总和从 0 变成 495。这条分支探完了,接下来要往回退到 9,去看它还没走的另一个孩子。
11. 13cur 恢复成 49从 5 退回 9:cur 自动恢复成上层的 49(按值传参的好处)。5 这格标记成已探完(变灰)。9 还有个右孩子 1 没走,带着 cur=49 去探它。
12. 14cur = 49*10 + 1 = 491进入 1,cur 更新成 49×10+1 = 491。注意 cur 是从恢复后的 49 算的,不会带上刚才 5 那条的痕迹。同样先判:1 是叶子吗?
13. 151 左右都空 → 是叶子!1 左右都没孩子 → 是叶子,路径 4→9→1 拼出 491,走到头,结算第二条。
14. 16总和 = 495 + 491 = 986把 491 加进总和,总和从 495 变成 986。1 探完,9 的左右孩子都走过了——该退回 9,再退回根 4 了。
15. 17cur 恢复成 41 探完退回 9,9 的两个孩子全灰了(整片探完),再从 9 退回根 4,cur 一路恢复成 4。整棵左子树(9 那一片)已探完(全灰)。
16. 184 左边走完,轮到右孩子 04 的左孩子 9 整片探完了。DFS 的规矩:左边走干净了才回头走右边。现在 cur=4,轮到 4 的右孩子 0。
17. 194 有孩子 → 不是叶子,合并左右结果根 4 本身有孩子,不是叶子,所以 4 自己从不被结算——它的结果是「左子树之和 + 右子树之和」。左边 986 已到手,带着 cur=4 去探右孩子 0。
18. 20cur = 4*10 + 0 = 40进入 0,cur 更新成 4×10+0 = 40。判一句:0 是叶子吗?
19. 210 左右都空 → 是叶子!0 左右都没孩子 → 是叶子,路径 4→0 拼出 40,第三条也走到头了。
20. 22总和 = 986 + 40 = 1026把 40 加进总和,总和变成 1026。0 探完,退回 4——此时 4 的左右孩子都走过了,整棵树遍历结束。
21. 23答案 = 495 + 491 + 40 = 1026三条路径数字 495、491、40 全部加完,答案 1026。核心就一句:DFS 沿路 cur=cur*10+val,到叶子把 cur 加进总和。
22. 24走完 5 退回 9 时,cur 自动是 49 而不是 495——因为传进 5 的那个 495 是「副本」,9 这层手里的 cur 一直是 49。这就是「按值传参」省掉手动回溯的原理。
23. 27本题携带的是「拼出的数字」;LC112/113 携带的是「路径和」;LC1448 携带的是「路上最大值」。换汤不换药——DFS 沿路带个累积量,到叶子做判定/结算,这一套能打通一大片树形题。
24. 29错误: 中间节点 4 / 49 也被加进总和如果忘了判叶子,走到 4 就加个 4、走到 9 又加个 49……半截数全混进总和。必须确认「左右孩子都为空」才结算,只有叶子手里的 cur 才是一条完整路径数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def sumNumbers(self, root):
        def dfs(node, cur):
            if not node:
                return 0
            cur = cur * 10 + node.val      # 拼上当前位
            if not node.left and not node.right:  # 叶子
                return cur                 # 这条路径的完整数
            return dfs(node.left, cur) + dfs(node.right, cur)
        return dfs(root, 0)

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
    int dfs(TreeNode* node, int cur) {
        if (!node) return 0;
        cur = cur * 10 + node->val;            // 拼上当前位
        if (!node->left && !node->right)       // 叶子
            return cur;                        // 完整数
        return dfs(node->left, cur) + dfs(node->right, cur);
    }
};

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node, int cur) {
        if (node == null) return 0;
        cur = cur * 10 + node.val;             // 拼上当前位
        if (node.left == null && node.right == null)  // 叶子
            return cur;                        // 完整数
        return dfs(node.left, cur) + dfs(node.right, cur);
    }
}

复杂度

面试官可能追问