17 ms O(n) java Prefix sum method
So the idea is similar as Two sum, using HashMap to store ( key : the prefix sum, value : how many ways get to this prefix sum) , and whenever reach a node, we 
So the idea is similar as Two sum, using HashMap to store ( key : the prefix sum, value : how many ways get to this prefix sum) , and whenever reach a node, we check if prefix sum - target exists in hashmap or not, if it does, we added up the ways of prefix sum - target into res.\nFor instance : in one path we have 1,2,-1,-1,2, then the prefix sum will be: 1, 3, 2, 1, 3, let's say we want to find target sum is 2, then we will have{2}, {1,2,-1},  {2,-1,-1,2} and {2}ways.\n\nI used global variable count, but obviously we can avoid global variable by passing the count from bottom up. The time complexity is O(n). This is my first post in discuss, open to any improvement or criticism. :)\n\n```\n    public int pathSum(TreeNode root, int sum) {\n        HashMap<Integer, Integer> preSum = new HashMap();\n        preSum.put(0,1);\n        helper(root, 0, sum, preSum);\n        return count;\n    }\n    int count = 0;\n    public void helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {\n        if (root == null) {\n            return;\n        }\n        \n        currSum += root.val;\n\n        if (preSum.containsKey(currSum - target)) {\n            count += preSum.get(currSum - target);\n        }\n        \n        if (!preSum.containsKey(currSum)) {\n            preSum.put(currSum, 1);\n        } else {\n            preSum.put(currSum, preSum.get(currSum)+1);\n        }\n        \n        helper(root.left, currSum, target, preSum);\n        helper(root.right, currSum, target, preSum);\n        preSum.put(currSum, preSum.get(currSum) - 1);\n    }\n```\n\nThanks for your advice, @StefanPochmann . Here is the modified version, concise and shorter:\n```\n    public int pathSum(TreeNode root, int sum) {\n        HashMap<Integer, Integer> preSum = new HashMap();\n        preSum.put(0,1);\n        return helper(root, 0, sum, preSum);\n    }\n    \n    public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {\n        if (root == null) {\n            return 0;\n        }\n        \n        currSum += root.val;\n        int res = preSum.getOrDefault(currSum - target, 0);\n        preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);\n        \n        res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);\n        preSum.put(currSum, preSum.get(currSum) - 1);\n        return res;\n    }\n```
[]