Java DFS Linear Solution using HashMap + Prefix Sum with Detailed Explanations
Intuition\nWhen talking about the path sum in a binary tree, we can easily think of 112. Path Sum and 113. Path Sum II. However, these two questions both focus 
# Intuition\nWhen talking about the path sum in a binary tree, we can easily think of [112. Path Sum](https://leetcode.com/problems/path-sum/) and [113. Path Sum II](https://leetcode.com/problems/path-sum-ii/). However, these two questions both focus on root-to-leaf paths only, whose path sum can be easily represented by a single variable `pathSum`. In this case we can use either a simple recursion, or DFS, to solve them with slight modification of `pathSum` in the recursion calls.\n\nThis problem, however, focuses on not only the root-to-leaf paths; instead, it focuses on any "parent-to-child" path (which include all root-to-leaf paths and all their sub-paths) with `pathSum == targetSum`. The good news is that we don\'t need to output all the paths; we only need to count the number of paths that satisfy the condition. In this case, it is actually an extension of [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/). If you are not familiar with the prefix sum algorithm, I suggest referring to [my solution to 560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/discuss/3313072/Java-2-Solutions-Cumulative-Sum-Prefix-Sum-%2B-HashMap-with-Detailed-Explanations) before further reading this solution.\n\nThe difference between this problem and [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/) is only the input data structure - it is given in the format of a binary tree instead of an array. In this case, we need to use depth-first search (DFS) to implement the algorithm.\n\nIf you are not familiar with using DFS in a binary tree, I suggest referring to [my solution to 113. Path Sum II](https://leetcode.com/problems/path-sum-ii/discuss/4689968/Java-DFS-Solution-(Beats-99.8)-with-Detailed-Explanations-and-Follow-Up-Question) before further reading this solution.\n\n# Approach\nSimilar to [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/), we still need to use a hashmap to store the prefix sum that we have encountered (key is the prefix sum on the path, and value is the corresponding counter). We also need a variable `currSum` to record the prefix sum from the upmost root to this current node. When we visit a new node, we need to examine the following two scenarios:\n\n- Scenario 1: Check whether the entire path has the desired sum (`currSum == targetSum`). If yes, we simply increment our result.\n- Scenario 2:  Check whether there is a "subpath" with the desired sum. Assume the entire path is [p1, p2, ..., pj], and [pi..j] has the desired sum, then [p1..i-1] will have a sum of `currSum - targetSum`. If the hashmap contains `currSum - targetSum`, we add the corresponding value to our result. \n\nThen we continue with DFS calls, but don\'t forget to reset the hashmap after the recursion calls.\n\nNote that the path sum can overflow the range of "int" in Java. To solve this problem we need to use "long" as the key.\n\u200B\n# Complexity\n- Time complexity: $$O(n)$$\n\u200B\n- Space complexity: $$O(n)$$\n\u200B\n# Code\n```\nclass Solution {\n    public int pathSum(TreeNode root, int targetSum) {\n        int[] ans = {0};\n        Map<Long, Integer> prefixSum = new HashMap<>();\n        dfs(root, prefixSum, 0, targetSum, ans);\n        return ans[0];\n    }\n    \n    \n    private void dfs(TreeNode root, Map<Long, Integer> prefixSum, long currSum, int targetSum, int[] ans) {\n        // Base case\n        if (root == null) {\n            return;\n        }\n        // Update curSum\n        currSum += root.val;\n        // Scenario 1: Check whether the entire path has the desired sum\n        if (currSum == targetSum) {\n            ans[0]++;\n        }\n        // Scenario 2: Check whether there is a "subpath" with the desired sum\n        // Assume the entire path is [p1, p2, ..., pj], and [pi..j] has the desired sum\n        // Then [p1..i-1] will have a sum of currSum - targetSum, which can be obtained from the hashmap\n        ans[0] += prefixSum.getOrDefault(currSum - targetSum, 0);\n        \n        // Update hashmap\n        prefixSum.put(currSum, prefixSum.getOrDefault(currSum, 0) + 1);\n        \n        // Recursion calls\n        dfs(root.left, prefixSum, currSum, targetSum, ans);\n        dfs(root.right, prefixSum, currSum, targetSum, ans);\n        \n        // Reset hashmap after recursion calls\n        prefixSum.put(currSum, prefixSum.get(currSum) - 1);\n    }\n}\n```
['Tree', 'Depth-First Search', 'Recursion', 'Binary Tree', 'Prefix Sum', 'Java']