My detailed explanation to the HashMap method
This is a recursion problem involved tree and HashMap. It requires a through understanding of recursion. I am surprised that this problem is categorized to "eas
This is a recursion problem involved tree and HashMap. It requires a through understanding of recursion. I am surprised that this problem is categorized to "easy" in LeetCode. \n\nA simple version of this problem: each node represents a number and find out **whether** existing a path that sums to a given number. Let's call it Problem A. \n\nA further simplified problem: given an array, find out whether existing a subarray whose sum is a given number. Let's call it Problem B.\n\nHow to solve Problem B? The idea is to use a HashSet to store prefix sum. Iteratively scan each number in the array and calculate the current sum, then check if `curSum - target` exists in the HashSet, if so return true; otherwise add curSum to the HashSet. Maybe you can get the idea quickly from the code: \n\n```\n// input parameters: int[] nums, int target\nSet<Integer> set = new HashSet<>();\ncurSum = 0;\nfor (int i : nums) {\n\tcurSum += i;\n\tif (set.contains(curSum - target)) {\n\t\treturn true;\n\t} else {\n\t\tset.add(curSum);\n\t}\n}\nreturn false;\n```\n  \nNow you can see that, after `nums[i]` is visited, the HashSet stores prefix sums from 0th element to the 0th element, 1st element, 2nd element, ... , ith element. If `curSum - target` exists in the HashSet, it means there is one subarray ended at current element, whose sum is `target`. Time complexity is O(n) and space complexity is O(n).\n\nNow let's go to Problem A. Because array is 1D data structure and tree is 1.5D data structure, so the idea to use a HashSet to store the prefix sum also works on Problem A. So the HashSet stores all the prefix sum corresponding to the current node, when visiting the node, calcuate the currrent sum then check if `curSum - target` exists in the HashSet. One thing worthes mention: if the node's value can be negative, when returning from a child node to its parent node, the HashSet needs to be updated as following:\n\n1. from the HashSet, remove the `curSum` of the child, if it is added to the HashSet successfully when visiting the child node,\n2.  do nothing to the HashSet if the `curSum` of the child can not add to the HashSet when visiting the child node(menas the number `curSum` already exists).\n\nIf all nodes' values are positive, then just remove `curSum` when it goes back to the parent node. The key point here is that make sure the HashSet is always correctly updated when iterating the tree.\n\nNow it is time for the original problem which requires the number of paths. Because nodes' values can be negative, it means that there might be multiple paths whose sum is the given value. So we need to use a HashMap whose key is the prefix sum and the value is the corresponding frequency.  Thanks to @kekezi for her clean code.\n\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode(int x) { val = x; }\n * }\n */\npublic class Solution {\n    public int pathSum(TreeNode root, int sum) {\n        if (root == null) {\n            return 0;\n        }\n        Map<Integer, Integer> map = new HashMap<>();\n        // if sum == target, map.get(sum - target) return 1\n        map.put(0, 1);\n        return findPathSum(root, 0, sum, map);\n    }\n    \n    private int findPathSum(TreeNode curr, int sum, int target, Map<Integer, Integer> map) {\n        if (curr == null) {\n            return 0;\n        }\n        // update the prefix sum by adding the current val\n        sum += curr.val;\n        // get the number of valid path, ended by the current node\n        int numPathToCurr = map.getOrDefault(sum - target, 0); \n        // update the map with the current sum, so the map is good to be passed to the next recursion\n        map.put(sum, map.getOrDefault(sum, 0) + 1);\n        // add the 3 parts discussed in 8. together\n        int res = numPathToCurr + findPathSum(curr.left, sum, target, map) + findPathSum(curr.right, sum, target, map);\n        // restore the map, as the recursion goes from the bottom to the top\n        map.put(sum, map.get(sum) - 1);\n        return res;\n    }\n}\n```\nTime complexity is O(n) and space complexity is O(h) where h is the height of tree and worst case it can be n.
[]