[Python] One-pass DFS, faster than 99%
Please feel free to give suggestions or ask questions. Upvote if you like the solution.\nO(h) space if we delete zero-valued items from sums.\n\nIdea: Maintain 
Please feel free to give suggestions or ask questions. **Upvote** if you like the solution.\nO(h) space if we delete zero-valued items from sums.\n\n**Idea**: Maintain prefix sums while doing dfs from root to leaf. If currentSum-prefixSum=targetSum, then we\'ve found a path that has a value of target. If we encountered prefixSum n times, then we\'ve found n such paths.\n```\ndef pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n\n\t# prefix sums encountered in current path\n\tsums = defaultdict(int)\n\tsums[0] = 1\n\n\tdef dfs(root, total):\n\t\tcount = 0\n\t\tif root:\n\t\t\ttotal += root.val\n\t\t\t# Can remove sums[currSum-targetSum] prefixSums to get target\n\t\t\tcount = sums[total-targetSum]\n\n\t\t\t# Add value of this prefixSum\n\t\t\tsums[total] += 1\n\t\t\t# Explore children\n\t\t\tcount += dfs(root.left, total) + dfs(root.right, total)\n\t\t\t# Remove value of this prefixSum (path\'s been explored)\n\t\t\tsums[total] -= 1\n\n\t\treturn count\n\n\treturn dfs(root, 0)\n```
['Depth-First Search', 'Prefix Sum', 'Python', 'Python3']