437. Path Sum III

https://leetcode.com/problems/path-sum-iii/description/

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        unordered_map<int,int> sums;
        sums[0] = 1;
        return dfs(root, sums, sum, 0);
    }
    int dfs(TreeNode* root, unordered_map<int,int>& sums, int target, int curSum) {
        int res = 0;
        if (root == NULL)   return res;
        curSum += root->val;
        res += sums[curSum-target];
        
        sums[curSum]++;
        res += dfs(root->left, sums, target, curSum);
        res += dfs(root->right, sums, target, curSum);
        sums[curSum]--;
        
        return res;
    }
};