1
class Solution {
2
  public int pathSum(TreeNode root, int targetSum) {
3
    HashMap<Long, Integer> hm = new HashMap<>();
4
    // hm.put(0L,1); ---> can use this to handle initial condition if c_sum == target sum
5

6
    int res = solve(hm, root, targetSum, 0);
7

8
    return res;
9
  }
10

11
  public int solve(HashMap<Long, Integer> hm, TreeNode node, long tgt, long c_sum) {
12

13
    if (node == null) return 0;
14

15
    c_sum += node.val;
16

17
    int res = 0;
18

19
    if (c_sum == tgt) // --> either this condition or the above commented condition.
20
    res++;
21

22
    if (hm.containsKey(c_sum - tgt)) {
23
      res += hm.get(c_sum - tgt);
24
    }
25

26
    hm.put(c_sum, hm.getOrDefault(c_sum, 0) + 1);
27

28
    int left = solve(hm, node.left, tgt, c_sum);
29
    int right = solve(hm, node.right, tgt, c_sum);
30

31
    res += (left + right);
32

33
    hm.put(c_sum, hm.getOrDefault(c_sum, 0) - 1); // remove the calculated cumulative sum
34

35
    return res;
36
  }
37
}