路径总和 III 图解题解

这道题到底在问什么

root

[10,5,-3,3,2,null,11,3,-2,null,1]

target

8

输出

3

先想最直接的笨办法

把这一刻拆开看：我不是去枚举起点，而是反过来问——之前哪个前缀和等于 18 减 8。表里 10 对应 1，就说明有 1 条以当前节点结尾、和为 8 的路径。这一步把 O(n) 的回溯枚举压成了一次 O(1) 查表，是全题的灵魂。（动画第 9 步）

最优解：一步一步想明白

1. 3最直接的想法：以每个节点为起点，再往下走一遍累加，看能不能凑到 target。一共 n 个起点、每条往下又是 O(n)，最坏 O(n²)。能过，但慢，而且重复加了一遍又一遍。
2. 4换个角度。记 cur 是「从根一路加到当前节点」的前缀和。如果这条根到当前的路径上，某个更早的位置前缀和等于 cur−target，那么从那之后到当前这一段，和就正好是 target。于是问题变成：cur−target 在表里出现过几次。
3. 5我们维护一张哈希表，键是前缀和，值是它在「当前这条根到节点的路径」上出现了几次。一开始放一个 0 出现 1 次，代表「空前缀」，这样从根直接出发、整段正好等于 target 的路径也能被数到。
4. 6cur=10，要找 cur−target = 10−8 = 2进入根节点 10。前缀和 cur 变成 10，要找 10−8=2，表里没有 2，不命中。然后把 10 记进表：现在表是 0 一次、10 一次。
5. 7cur=15，要找 15−8 = 7走到左孩子 5，前缀和累加到 15，要找 7。表里只有 0、10，没有 7，不命中。把 15 记进表。
6. 8cur=18，要找 18−8 = 10，表里 10 出现 1 次 ✓走到节点 3，前缀和到 18，要找 18−8=10。表里 10 出现过 1 次！这意味着从「前缀和为 10 的位置」之后到现在，正好和为 8，也就是路径 5→3。答案加 1。
7. 9ans += prefix[cur−target] = prefix[10] = 1把这一刻拆开看：我不是去枚举起点，而是反过来问——之前哪个前缀和等于 18 减 8。表里 10 对应 1，就说明有 1 条以当前节点结尾、和为 8 的路径。这一步把 O(n) 的回溯枚举压成了一次 O(1) 查表，是全题的灵魂。
8. 10cur=21，要找 21−8 = 13再往下到这个 3，前缀和 21，要找 13，表里没有，不命中。这条分支到此结束，接下来要往回走了。
9. 11返回时 prefix[21] −= 1，把 21 从表里抹掉这是和数组前缀和最不一样的地方：树会分叉。离开一个节点往回走时，必须把它贡献的前缀次数减回去。否则等会儿走到兄弟分支，会误把「不在这条路径上」的 21 当成可用前缀，凭空多数路径。
10. 12cur=18，要找 10，表里 10 仍在 ✓回到 5，改走右边的 2 再到 1，前缀和又是 18，找 10 再次命中。这条路径是 5→2→1，同样和为 8。答案到 2。注意刚才撤销了 21，表是干净的，没有串味。
11. 13cur=18，要找 10，又命中 ✓左子树彻底退完后，表又回到只剩根的状态，走右子树 -3 再到 11。10 减 3 加 11，前缀和还是 18，找 10 第三次命中，路径 -3→11。答案到 3。
12. 14三条命中路径，共 ans = 3所有节点进出 DFS 一遍，三次命中标成绿色。整棵树只走了一遍，答案是 3。
13. 17一句话本质：不要枚举起点，而是用「当前前缀 cur 减去 target」去表里查历史前缀出现了几次。数组前缀和搬到树上，唯一多出来的就是「回溯撤销」。
14. 22把这题练到能脱稿复述后，去同类题里迁移：先复用「前缀和 → 次数」的状态定义，再按新题调整边界。也可以让 AI 助教小欧出一道变体、或进通关训练里实战一遍。

⚠️ 容易写错的地方

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

class Solution:
    def pathSum(self, root, targetSum):
        prefix = {0: 1}        # 前缀和 -> 次数
        self.ans = 0
        def dfs(node, cur):
            if not node:
                return
            cur += node.val
            self.ans += prefix.get(cur - targetSum, 0)
            prefix[cur] = prefix.get(cur, 0) + 1
            dfs(node.left, cur)
            dfs(node.right, cur)
            prefix[cur] -= 1        # 回溯撤销
        dfs(root, 0)
        return self.ans

class Solution {
    unordered_map<long, int> prefix;
    int target = 0, ans = 0;
    void dfs(TreeNode* node, long cur) {
        if (!node) return;
        cur += node->val;
        if (prefix.count(cur - target)) ans += prefix[cur - target];
        prefix[cur]++;
        dfs(node->left, cur);
        dfs(node->right, cur);
        prefix[cur]--;        // 回溯撤销
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        target = targetSum;
        prefix[0] = 1;
        dfs(root, 0);
        return ans;
    }
};

class Solution {
    Map<Long, Integer> prefix = new HashMap<>();
    int target = 0, ans = 0;
    void dfs(TreeNode node, long cur) {
        if (node == null) return;
        cur += node.val;
        ans += prefix.getOrDefault(cur - target, 0);
        prefix.merge(cur, 1, Integer::sum);
        dfs(node.left, cur);
        dfs(node.right, cur);
        prefix.merge(cur, -1, Integer::sum);   // 回溯撤销
    }
    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        prefix.put(0L, 1);
        dfs(root, 0);
        return ans;
    }
}

# 适用：统计「向下路径和 = target」的条数
prefix = {0: 1}          # 1) 初始空前缀
ans = 0
def dfs(node, cur):
    if not node: return
    cur += node.val      # 2) 累加当前前缀
    ans += prefix.get(cur - target, 0)   # 3) 查 cur-target
    prefix[cur] = prefix.get(cur, 0) + 1 # 4) 记入表
    dfs(node.left, cur); dfs(node.right, cur)
    prefix[cur] -= 1     # 5) 回溯撤销(树专属)

// 适用：统计向下路径和 == target 的条数
unordered_map<long,int> prefix;  // 前缀和 -> 次数
long target; int ans = 0;
void dfs(TreeNode* node, long cur) {
    if (!node) return;
    cur += node->val;                  // 2) 累加
    if (prefix.count(cur - target))    // 3) 查表
        ans += prefix[cur - target];
    prefix[cur]++;                     // 4) 记入
    dfs(node->left, cur); dfs(node->right, cur);
    prefix[cur]--;                     // 5) 撤销
}

// 适用：统计向下路径和 == target 的条数
Map<Long,Integer> prefix = new HashMap<>();
long target; int ans = 0;
void dfs(TreeNode node, long cur) {
    if (node == null) return;
    cur += node.val;                       // 2) 累加
    ans += prefix.getOrDefault(cur-target,0); // 3) 查表
    prefix.merge(cur, 1, Integer::sum);    // 4) 记入
    dfs(node.left, cur); dfs(node.right, cur);
    prefix.merge(cur, -1, Integer::sum);   // 5) 撤销

复杂度

面试官可能追问