Problem
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).
Examples
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
Solution
Method 1 - Using Prefix sum and hashmap
So the idea is similar as Two Sum Problem, using HashMap to store ( key : the prefix sum, value : how many ways get to this prefix sum).
So, for each node, we check if prefix sum - target exists in hashmap or not, if it does, we added up the ways of prefix sum - target into ans.
For instance : in one path we have [1,2,-1,-1,2]
, then the prefix sum will be: [1, 3, 2, 1, 3]
, let’s say we want to find target sum is 2, then we will have [[2], [1,2,-1], [2,-1,-1,2] and [2]]
aka 4 ways.
Code
Java
class Solution {
public int pathSum(TreeNode root, int sum) {
Map<Integer, Integer> map = new HashMap();
map.put(0,1);
return helper(root, 0, sum, map);
}
public int helper(TreeNode root, int currSum, int target, Map<Integer, Integer> map) {
if (root == null) {
return 0;
}
currSum += root.val;
int ans = map.getOrDefault(currSum - target, 0);
map.put(currSum, map.getOrDefault(currSum, 0) + 1);
ans += helper(root.left, currSum, target, map) + helper(root.right, currSum, target, map);
map.put(currSum, map.get(currSum) - 1);
return ans;
}
}
Complexity
- Time:
O(n)
- Space:
O(n)
Method 2 - Using DFS
Code
Java
public class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int dfs(TreeNode node, int sum) {
if (node == null) {
return 0;
}
return (node.val == sum ? 1 : 0)
+ dfs(node.left, sum - node.val) + dfs(node.right, sum - node.val);
}
}
Complexity
- Time:
O(n^2)
- Space:
O(n)
due to recursion stack