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 Explanation: The paths that sum to 8 are shown.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: 3
Constraints:
[0, 1000].-109 <= Node.val <= 109-1000 <= targetSum <= 1000This approach uses a combination of DFS and path sum calculation. For each node, calculate the sum of all paths that end at the current node. This is achieved recursively
This recursive solution calculates the number of paths that sum to the targetSum starting from each node. The function pathSumFrom checks both left and right paths recursively
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) in the worst case. Space Complexity: O(n) due to the function call stack.
This approach leverages a hashmap to store cumulative sums and uses them to find paths that lead to the targetSum.
This solution uses a hashmap called prefix to capture the number of ways to obtain each cumulative sum that ends at a node. When a node is visited, the difference between the current cumulative sum and the target is used to check for matching sums encountered earlier.
Java
Time Complexity: O(n). Space Complexity: O(n), where n is the number of nodes in the tree.
| Approach | Complexity |
|---|---|
| Using Depth-First Search (DFS) and Path Sum Calculation | Time Complexity: O(n^2) in the worst case. Space Complexity: O(n) due to the function call stack. |
| Using Hashmap to Store Prefix Sums | Time Complexity: O(n). Space Complexity: O(n), where n is the number of nodes in the tree. |
Path Sum - Leetcode 112 - Python • NeetCode • 78,794 views views
Watch 9 more video solutions →Practice Path Sum III with our built-in code editor and test cases.
Practice on FleetCode