1
class Solution {
2
 public:
3
  int ans = 0, t;
4

5
  void dfs(unordered_map<long long, int> &curr, TreeNode *node, long long sm) {
6
    if (!node) {
7
      return;
8
    }
9

10
    sm += (long long)node->val;
11
    ans += curr[sm - t];
12
    curr[sm]++;
13

14
    dfs(curr, node->left, sm);
15
    dfs(curr, node->right, sm);
16

17
    curr[sm]--;
18
  }
19
  int pathSum(TreeNode *root, int targetSum) {
20
    if (!root) {
21
      return 0;
22
    }
23

24
    t = targetSum;
25
    unordered_map<long long, int> curr;
26
    curr[0] = 1;
27
    long long sm = 0;
28

29
    dfs(curr, root, sm);
30

31
    return ans;
32
  }
33
};