[JAVA] 100% Faster [HashMap] [Cumulative Sum]
This is similar to finding subarray sum equal to target. \n\nIn this example, different arrays are paths from root to all leaves\n\n[10,5,3,3]\n[10,5,3,-2]\n[10
This is similar to finding subarray sum equal to target. \n![image](https://assets.leetcode.com/users/images/fe07abf7-6531-4998-bdd8-9c842aacc5d0_1596892479.6344945.png)\nIn this example, different arrays are paths from root to all leaves\n```\n[10,5,3,3]\n[10,5,3,-2]\n[10,5,2,1]\n[10,-3,11]\n```\n\nInstead of storing all the subarrays, we just calculate the cumulative sum from root to that node using **cSum**. Also, keep track of all the sums seen so far from root to that node in hashmap **map**. The hashmap stores the sum seen so far and the count (how many times that sum is found).\nAfter traversing left and right subtrees, we have to backtrack by reduce count from hashmap.\n\n```\nclass Solution {\n    int result;\n    public int pathSum(TreeNode root, int sum) {\n        HashMap map = new HashMap<Integer,Integer>();\n      \n        result = 0;\n        map.put(0,1);\n        pathSumUtil(map,root,0,sum);\n        return result;\n    }\n    \n    void pathSumUtil(HashMap<Integer,Integer> map, TreeNode root,int cSum,int sum){\n        if(root == null)\n            return;\n\t\t// calculate cumulative sum\n        int temp = cSum+root.val;\n        if(map.containsKey(temp-sum))\n            result+= map.get(temp-sum);\n        \n\t\t// add the sum seen so far in hashmap\n        map.put(temp,map.getOrDefault(temp,0)+1);\n        // recur for left and right subtrees \n        if(root.left != null) pathSumUtil(map,root.left,cSum+root.val,sum);\n        if(root.right != null) pathSumUtil(map,root.right,cSum+root.val,sum);\n\t\t// backtrack\n        map.put(temp,map.get(temp)-1);\n    }\n}\n```
[]