2 ms, faster than 100.00% | JAVA | HashMap | O(n) | Prefix Sum
\nclass Solution {\n\n    public int pathSum(TreeNode root, int targetSum) {\n        int[] ans = new int[1];\n        Map<Integer,Integer> map = new HashMap<>(
```\nclass Solution {\n\n    public int pathSum(TreeNode root, int targetSum) {\n        int[] ans = new int[1];\n        Map<Integer,Integer> map = new HashMap<>(); // to store all prefix sum\n        map.put(0,1); // to handle case where currSum == target\n        traverse(root,0,map,ans,targetSum);\n        return ans[0];\n \n    }\n    \n    public void traverse(TreeNode root, int currSum, Map<Integer,Integer> map, int[] ans, int targetSum){\n        if(root == null)\n            return;\n        currSum+=root.val;\n        \n        if(map.containsKey(currSum - targetSum) && map.get(currSum - targetSum) > 0)\n            ans[0]+=map.get(currSum - targetSum);\n        map.put(currSum,map.getOrDefault(currSum,0)+1);\n        traverse(root.left, currSum, map, ans,targetSum);\n        traverse(root.right, currSum, map, ans, targetSum);\n        map.put(currSum,map.getOrDefault(currSum,0)-1); // backtrack\n\n    }\n}\n```
['Java']