O(n) java solution
This is a variation of https://leetcode.com/problems/subarray-sum-equals-k/. For key intuition/approach, please refer to that problem, as it\'s easier to unders
This is a variation of https://leetcode.com/problems/subarray-sum-equals-k/. For key intuition/approach, please refer to that problem, as it\'s easier to understand than the current problem.\n\nOnly diff is the sums are unique to each path, hence every time we finish a recursive call, we should remove the current sum from it so other paths don\'t end up with irrelevant sums:\n\n\tclass Solution {\n\t\tint count = 0, target = 0;\n\t\tpublic int pathSum(TreeNode root, int sum) {\n\t\t\ttarget = sum;\n\t\t\tMap<Integer, Integer> sumMap = new HashMap<>();\n\t\t\tsumMap.put(0, 1);\n\t\t\tcount(root, 0, sumMap);\n\t\t\treturn count;\n\t\t}\n\n\t\tprivate void count(TreeNode n, int sum, Map<Integer, Integer> prevSums) {\n\t\t\tif (n == null) return;\n\t\t\tsum += n.val;\n\t\t\tcount += prevSums.getOrDefault(sum - target, 0);\n\n\t\t\tprevSums.put(sum, prevSums.getOrDefault(sum, 0) + 1);\n\t\t\tcount(n.left, sum, prevSums);\n\t\t\tcount(n.right, sum, prevSums);\n\t\t\tprevSums.put(sum, prevSums.getOrDefault(sum, 0) - 1);\n\t\t}\n\t}
[]