437: Space 93.92%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Define the function with the given input parameters: a binary tree roo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Define the function with the given input parameters: a binary tree root node and an integer targetSum. The function should return an integer representing the number of paths in the tree that sum to the targetSum.\n\n2. Create a class variable called count and initialize it to 0. This variable will keep track of the number of paths that sum to the targetSum.\n\n3. Create a dictionary called prefix_sum and initialize it with a key-value pair of 0 and 1. This dictionary will keep track of the prefix sum values and the number of times they occur in the path.\n\n4. Define a recursive helper function called dfs that takes three parameters: a node in the binary tree, the targetSum, and the current sum of the path. This function will perform a depth-first search on the binary tree.\n\n5. If the current node is None, return.\n\n6. Add the value of the current node to the current sum.\n\n7. Check if the difference between the current sum and the targetSum is present in the prefix_sum dictionary. If it is, add the value of the key to the count variable.\n\n8. Add the current sum to the prefix_sum dictionary with a value of 1 if it is not already present. If it is present, increment the value by 1.\n\n9. Recursively call the dfs function on the left child of the current node with the updated current sum.\n\n10. Recursively call the dfs function on the right child of the current node with the updated current sum.\n\n11. Decrement the value of the current sum in the prefix_sum dictionary by 1, as this node is no longer in the path.\n\n12. Call the dfs function on the root node with a current sum of 0.\n\n13. Return the count variable.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n        self.count = 0\n        self.prefix_sum = {0: 1}\n        self.dfs(root, targetSum, 0)\n        return self.count\n        \n    def dfs(self, node: TreeNode, targetSum: int, curr_sum: int) -> None:\n        if not node:\n            return\n        \n        curr_sum += node.val\n        self.count += self.prefix_sum.get(curr_sum - targetSum, 0)\n        self.prefix_sum[curr_sum] = self.prefix_sum.get(curr_sum, 0) + 1\n        \n        self.dfs(node.left, targetSum, curr_sum)\n        self.dfs(node.right, targetSum, curr_sum)\n        \n        self.prefix_sum[curr_sum] -= 1\n\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'Python3']