437. 路径总和 III

难度：🟡 Medium | 标签：树、前缀和、DFS | 状态：⬜ LeetCode 链接

思路

类比 560（和为 K 的子数组）：从根到当前节点的前缀和 sum，查 sum - target 在路径上出现过几次。

DFS 维护哈希计数 前缀和 → 出现次数，回溯时减回去。

代码

class Solution {
    unordered_map<long long, int> mp;
    int target;
    int dfs(TreeNode* r, long long cur) {
        if (!r) return 0;
        cur += r->val;
        int cnt = 0;
        auto it = mp.find(cur - target);
        if (it != mp.end()) cnt += it->second;
        mp[cur]++;
        cnt += dfs(r->left, cur) + dfs(r->right, cur);
        mp[cur]--;
        return cnt;
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        mp[0] = 1;
        target = targetSum;
        return dfs(root, 0);
    }
};

复杂度

• 时间 O(n)，空间 O(n)

易错 / 回顾

• 哈希初始 mp[0] = 1（前缀和本身等于 target）
• 回溯必须减回去，否则跨分支错算
• 用 long long 防累加溢出