Untitled

 avatar
unknown
plain_text
24 days ago
719 B
1
Indexable
class Solution {
  public int pathSum(TreeNode root, int sum) {
      HashMap<Integer, Integer> map = new HashMap();
      map.put(0,1);
      return pathSum2(root, 0, sum, map);
  }
    
  public int pathSum2(TreeNode root, int runningSum, int target, HashMap<Integer, Integer> map) {
      if (root == null) {
          return 0;
      }

      runningSum += root.val;
      int count = map.getOrDefault(runningSum - target, 0);
      map.put(runningSum, map.getOrDefault(runningSum, 0) + 1);

      count += pathSum2(root.left, runningSum, target, map) 
        + pathSum2(root.right, runningSum, target, map);
    
      map.put(runningSum, map.get(runningSum) - 1);
      return count;
  }
  
Leave a Comment