Problem
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the node values equals targetSum.A path must travel from a parent node to one of its child nodes, and it can start and end at any node in the tree. The path must always move downward.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
root:
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
targetSum = 8Output
3Example 2
Input
root:
5
/ \
4 8
/ / \
3 13 4
/ \ \
2 1 1
targetSum = 7Output
3Solution
This solution uses Prefix Sum with a HashMap. During the DFS traversal, we maintain the cumulative sum from the root to the current node.If the current prefix sum is
currentSum, we need to find an earlier prefix sum equal to currentSum - targetSum. The difference between these two prefix sums represents a downward path whose sum is exactly targetSum.
The HashMap stores how many times each prefix sum has occurred. After processing a node and its subtrees, we remove the current prefix sum from the map so that paths from different branches are not mixed.
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> prefixSumMap = new HashMap<>();
prefixSumMap.put(0L, 1);
return pathSumHelper(root, targetSum, 0L, prefixSumMap);
}
private int pathSumHelper(
TreeNode root,
int targetSum,
long currentSum,
Map<Long, Integer> prefixSumMap) {
if (root == null) {
return 0;
}
currentSum += root.val;
// Count paths ending at the current node.
int count = prefixSumMap.getOrDefault(currentSum - targetSum, 0);
prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);
count += pathSumHelper(root.left, targetSum, currentSum, prefixSumMap);
count += pathSumHelper(root.right, targetSum, currentSum, prefixSumMap);
// Backtrack the current prefix sum.
prefixSumMap.put(currentSum, prefixSumMap.get(currentSum) - 1);
return count;
}
}Complexity
Each node is visited once and the HashMap operations takeO(1) average time, so the time complexity is O(n), where n is the number of nodes.
The HashMap and DFS recursion use space proportional to the height of the tree in a balanced traversal, with up to
O(n) space in the worst case. Therefore, the extra space complexity is O(n).