Python easy DFS solution using Prefix Sum approach
This problem can be solved by applying same approach as problem 560 which used prefix-sum method. Both the solutions are given below.\n\nProblem 437 : Path Sum 
This problem can be solved by applying same approach as [problem 560](https://leetcode.com/problems/subarray-sum-equals-k/) which used prefix-sum method. Both the solutions are given below.\n\n**Problem 437 : [Path Sum III](https://leetcode.com/problems/path-sum-iii/)**\n\n```python\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\nclass Solution:\n    def pathSum(self, root: TreeNode, sum: int) -> int:\n        if not root:\n            return 0\n        \n        # Recursive DFS\n\t\t# Using Prefix Sum approach\n        \n        def dfs(node, curr_sum, sum):\n            if not node:\n                return 0\n            \n            res = 0\n            curr_sum += node.val\n            \n            if (curr_sum - sum) in mapping:\n                res += mapping[curr_sum - sum]\n            if curr_sum in mapping:\n                mapping[curr_sum] += 1\n            else:\n                mapping[curr_sum] = 1\n                \n            res += dfs(node.left, curr_sum, sum)\n            res += dfs(node.right, curr_sum, sum)\n            mapping[curr_sum] -= 1\n            \n            return res\n            \n        mapping = defaultdict(int)\n        mapping[0] = 1\n        return dfs(root, 0, sum)\n        \t\t\n```\n\n\n**Problem 560 : [Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)**\n\n```python\nclass Solution:\n    def subarraySum(self, nums: List[int], k: int) -> int:\n        # Time Complexity - O(n)\n        # Space Complexity - O(n)\n        curr_sum = res = 0\n        mapping = defaultdict(int)\n        for i in nums:\n            curr_sum += i\n            if (curr_sum - k) in mapping:\n                res += mapping[curr_sum - k]\n            mapping[curr_sum] += 1\n        res += mapping[k]\n        return res\n        \t\t\n```\n
['Tree', 'Depth-First Search', 'Recursion', 'Prefix Sum', 'Python', 'Python3']