Problem statement
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).
Problem statement taken from: https://leetcode.com/problems/path-sum-iii
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:
- The number of nodes in the tree is in the range [0, 1000].
- -10^9 <= Node.val <= 10^9
- -1000 <= targetSum <= 1000
Explanation
Recursion
The problem is similar to our previous blog posts Path Sum and Path Sum II.
We need to change the algorithm a bit to count the different paths in the tree. We will use the DFS algorithm to count the paths. Let's check the algorithm.
// pathSum method
- if root == null
- return 0
- return dfs(root, 0, targetSum) +
pathSum(root->left, targetSum) +
pathSum(root->right, targetSum)
// dfs method
- if root == null
- return 0
- set currentSum = previousSum + root->val
count = 0
- if currentSum == targetSum
- count = 1
- return count +
dfs(root->left, currentSum, targetSum) +
dfs(root->right, currentSum, targetSum)
The time-complexity can be reduced to O(nlog(n)) by reversing the linked list.
Let's check our algorithm in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
int dfs(TreeNode* root, long long previousSum, long long targetSum) {
if(root == NULL) {
return 0;
}
int currentSum = previousSum + root->val;
int count = 0;
if(currentSum == targetSum) {
count = 1;
}
return count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum);
}
int pathSum(TreeNode* root, int targetSum) {
if(root == NULL) {
return 0;
}
return dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
}
};
Golang solution
func dfs(root *TreeNode, previousSum, targetSum int) int {
if root == nil {
return 0
}
currentSum := previousSum + root.Val
count := 0
if currentSum == targetSum {
count = 1
}
return count + dfs(root.Left, currentSum, targetSum) + dfs(root.Right, currentSum, targetSum)
}
func pathSum(root *TreeNode, targetSum int) int {
if root == nil {
return 0
}
return dfs(root, 0, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}
Javascript solution
var dfs = function(root, previousSum, targetSum) {
if(root == null) {
return 0;
}
let currentSum = previousSum + root.val;
let count = 0;
if(currentSum == targetSum) {
count = 1;
}
return count + dfs(root.left, currentSum, targetSum) + dfs(root.right, currentSum, targetSum);
};
var pathSum = function(root, targetSum) {
if(root == null) {
return 0;
}
return dfs(root, 0, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
};
Let's dry-run our algorithm to see how the solution works.
Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]
targetSum = 8
// pathSum method
Step 1: if root == NULL
root -> 10
false
Step 2: dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum)
dfs(->10, 0, 8) + pathSum(->5, 8) + pathSum(-3, 8)
// dfs method
Step 3: if root == NULL
root -> 10
false
currentSum = previousSum + root->val
= 0 + 10
= 10
count = 0
currentSum == targetSum
10 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->5, 10, 8) + dfs(->(-3), 10, 8)
// dfs(->5, 10, 8)
Step 4: if root == NULL
root -> 5
false
currentSum = previousSum + root->val
= 10 + 5
= 15
count = 0
currentSum == targetSum
15 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->3, 15, 8) + dfs(2, 15, 8)
// dfs(->3, 15, 8)
Step 5: if root == NULL
root -> 3
false
currentSum = previousSum + root->val
= 15 + 3
= 18
count = 0
currentSum == targetSum
18 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->3, 18, 8) + dfs(->(-2), 18, 8)
// dfs(->3, 18, 8)
Step 6: if root == NULL
root -> 3
false
currentSum = previousSum + root->val
= 18 + 3
= 21
count = 0
currentSum == targetSum
21 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 21, 8) + dfs(->nil, 21, 8)
Both dfs(->nil, 21, 8), dfs(->nil, 21, 8) node is nil so we return 0 and backtrack to Step 5
0 + dfs(->3, 18, 8) + dfs(->(-2), 18, 8) where we solve for
dfs(->(-2), 18, 8)
// dfs(->(-2), 18, 8)
Step 7: if root == NULL
root -> -2
false
currentSum = previousSum + root->val
= 21 + -2
= 19
count = 0
currentSum == targetSum
19 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 19, 8) + dfs(->nil, 19, 8)
Both dfs(->nil, 19, 8), dfs(->nil, 19, 8) node is nil so we return 0 and backtrack to Step 4
0 + dfs(->3, 15, 8) + dfs(2, 15, 8) where we solve for
dfs(2, 15, 8)
// dfs(2, 15, 8)
Step 8: if root == NULL
root -> 2
false
currentSum = previousSum + root->val
= 15 + 2
= 17
count = 0
currentSum == targetSum
17 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 17, 8) + dfs(1, 17, 8)
dfs(->nil, 17, 8) returns 0 as node is nil, so we evaluate for
dfs(1, 17, 8)
// dfs(1, 17, 8)
Step 9: if root == NULL
root -> 1
false
currentSum = previousSum + root->val
= 17 + 1
= 18
count = 0
currentSum == targetSum
18 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 18, 8) + dfs(->nil, 18, 8)
Both dfs(->nil, 19, 8), dfs(->nil, 19, 8) node is nil so we return 0 and backtrack to Step 3
0 + dfs(->5, 10, 8) + dfs(->(-3), 10, 8) where we solve for
dfs(->(-3), 10, 8)
// dfs(->(-3), 10, 8)
Step 10: if root == NULL
root -> -3
false
currentSum = previousSum + root->val
= 10 + -3
= 7
count = 0
currentSum == targetSum
7 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 7, 8) + dfs(->11, 7, 8)
dfs(->nil, 7, 8) returns 0 as node is nil, so we evaluate for
dfs(->11, 7, 8)
// dfs(->11, 7, 8)
Step 11: if root == NULL
root -> 11
false
currentSum = previousSum + root->val
= 7 + 11
= 18
count = 0
currentSum == targetSum
18 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->nil, 18, 8) + dfs(->nil, 18, 8)
Both dfs(->nil, 18, 8), dfs(->nil, 18, 8) node is nil so we return 0 and backtrack to Step 2
dfs(->10, 0, 8) + pathSum(->5, 8) + pathSum(-3, 8)
where we have dfs(->10, 0, 8) as 0
and we evaluate for pathSum(->5, 8)
// pathSum(->5, 8)
Step 12: if root == NULL
root -> 5
false
dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum)
dfs(->5, 0, 8) + pathSum(->3, 8) + pathSum(->2, 8)
// dfs(->5, 0, 8)
Step 13: if root == NULL
root -> 5
false
currentSum = previousSum + root->val
= 0 + 5
= 5
count = 0
currentSum == targetSum
5 == 8
false
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
0 + dfs(->3, 5, 8) + dfs(->2, 5, 8)
// dfs(->3, 5, 8)
Step 14: if root == NULL
root -> 3
false
currentSum = previousSum + root->val
= 5 + 3
= 8
count = 0
currentSum == targetSum
8 == 8
true
count = 1
count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
1 + dfs(->3, 8, 8) + dfs(->(-2), 8, 8)
We similarly iterate over the rest of the tree and return the count.
Top comments (0)