[Python3] DFS + Dictionary - Simple Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\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\nclass Solution:\n    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n        d = collections.Counter()\n        d[0] = 1\n        \n        def dfs(node: Optional[TreeNode], s: int) -> int:\n            if not node: return 0\n            s += node.val\n            res =  d[s - targetSum]\n            d[s] += 1\n            res += dfs(node.left, s) + dfs(node.right, s)\n            d[s] -= 1\n            if d[s] == 0: del d[s]\n            return res\n        \n        return dfs(root, 0)\n```
['Hash Table', 'Depth-First Search', 'Python3']