面试必考精华版Leetcode437. 路径总和 III

题目：

---

代码（首刷看解析，暴力法）：

class Solution {
public:
    long rootSum(TreeNode* root,long targetSum){
        if(!root) return 0;
 
        long res=0;
        if(root->val==targetSum){
            res++;
        } 
 
        res+=rootSum(root->left,targetSum-root->val);
        res+=rootSum(root->right,targetSum-root->val);
        return res;
    }
    long pathSum(TreeNode* root, long targetSum) {
        if(!root) return 0;
        long res =rootSum(root,targetSum);
        res+=pathSum(root->left,targetSum);
        res+=pathSum(root->right,targetSum);
        return res;
    }
};

        int类型大小不够，需要long

---

代码(二刷看解析 前缀和 2024年3月6日）

class Solution {
public:
    int res;
    void recursion(TreeNode* root, const int target, long long prefix_sum, unordered_map<long long,int>& um) {
        if (!root) return;
 
        prefix_sum += root->val;
        res += um[prefix_sum - target];
 
        um[prefix_sum]++;
        recursion(root->left, target, prefix_sum, um);
        recursion(root->right, target, prefix_sum, um);
        um[prefix_sum]--;
    }
 
    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;
        unordered_map<long long, int> prefix_to_quantity;
        res = 0;
        prefix_to_quantity[0] = 1;
        recursion(root, targetSum, 0, prefix_to_quantity);
        return res;
    }
};