Python Solution | DFS | HashTable | O(n) Time | O(n) Space
Explanation\n- depth first search through each node\n- store the hash of prefix sum of the current path ([key -> prefix sum] : value -> count )\n- A path exist 
#### Explanation\n- depth first search through each node\n- store the hash of prefix sum of the current path ([key -> prefix sum] : value -> count )\n- A path exist when currentSum - prefixSum = sum, therefore occurence of prefixSum (currentSum - sum) in sumHash represents the number of paths ending at current node\n\n\n```\n# Definition for a binary tree node.\n# class TreeNode(object):\n#     def __init__(self, x):\n#         self.val = x\n#         self.left = None\n#         self.right = None\n\nclass Solution(object):\n    def pathSum(self, root, sum):\n        \n        def dfs(sumHash, prefixSum, node):\n\n            if not node:\n                return 0\n            \n\t\t\t# Sum of current path\n            prefixSum += node.val\n            \n\t\t\t# number of paths that ends at current node\n            path = sumHash[prefixSum - sum] \n            \n\t\t\t# add currentSum to prefixSum Hash\n            sumHash[prefixSum] += 1\n            \n\t\t\t# traverse left and right of tree\n            path += dfs(sumHash, prefixSum, node.left) + dfs(sumHash, prefixSum, node.right)\n        \n\t\t    # remove currentSum from prefixSum Hash\n            sumHash[prefixSum] -= 1\n            \n            return path\n        \n        # depth first search, initialize sumHash with prefix sum of 0, occurring once\n        return dfs(collections.defaultdict(int, {0: 1}), 0, root)\n        \n```
['Hash Table', 'Depth-First Search', 'Prefix Sum', 'Python', 'Python3']