Path Sum III
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).
Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Constraints:
- The number of nodes in the tree is in the range
[0, 1000]. - -109 <= Node.val <= 109
- -1000 <= targetSum <= 1000
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
The brute force approach involves iterating over each node and trying to find all paths starting from each node that sum up to the given targetSum. For each node, we perform a DFS traversal while counting paths that result in the targetSum.
Steps:
- For each node, you calculate path sums starting from the node itself.
- Use a helper function to recursively calculate path sums from the current node.
- Use another function to iterate over each node and treat it as a starting point.
Code:
- Time Complexity: O(n^2) where (n) is the number of nodes in the tree. In the worst case, each node is visited (n) times.
- Space Complexity: O(n) for the recursion stack in the worst case if the tree is completely unbalanced.
2. Prefix Sum Approach
Intuition:
This optimized approach uses a hashmap to store the prefix sum frequencies encountered so far while traversing the tree. The idea is to leverage the prefix sum technique to quickly find if there exists a subpath ending in the current node that sums up to the targetSum.
Steps:
- Use a recursive function to traverse the tree.
- For each node, calculate its prefix sum.
- Use a hashmap to check whether there exists a prefix sum such that removing it from the current prefix sum would give us the
targetSum. - Update the prefix sum count in the hashmap while going deeper into the recursion and undo changes when backtracking.
Code:
- Time Complexity: O(n) since each node is visited once.
- Space Complexity: O(n) for the hashmap storing the prefix sums and for the recursion stack in the worst case.