Problem Description
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Key Insights
- A path can start and end at any node, but must go downwards towards child nodes.
- We can use depth-first search (DFS) to explore all paths from each node.
- We can keep track of the cumulative sums using a hashmap (dictionary) to count how many times each sum has occurred.
Space and Time Complexity
Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once. Space Complexity: O(H), where H is the height of the tree due to the recursive call stack.
Solution
We will use a depth-first search (DFS) approach to traverse the binary tree, starting from each node. At each node, we will check all possible paths that can originate from that node and go downwards. We maintain a hashmap to keep track of the cumulative sums encountered so far, allowing us to efficiently check how many times we have seen the needed sum to form a valid path.