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 downward (from parent toward children).
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The three paths are: 5→3, 5→2→1, and -3→11. Each sums to 8.
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Constraints:
- 0 <= Number of nodes <= 1000
- -109 <= Node.val <= 109
- -1000 <= targetSum <= 1000
Contents
- Solution — Prefix Sum with HashMap
- Complexity Analysis
Prefix Sum with HashMap
The key insight mirrors the "subarray sum equals K" array problem. As we traverse from root to
a node, we maintain a running prefixSum. If prefixSum - targetSum
was seen earlier on this root-to-node path, then the subpath between that earlier node and the
current node sums to targetSum.
We store each prefix sum's frequency in a HashMap. We seed it with
{0: 1} to handle paths starting from the root.
Algorithm:
- Initialize prefixCount = {0: 1} and prefixSum = 0.
- At each node, add its value to prefixSum.
- Look up prefixSum - targetSum in the map — that count is added to the result.
- Increment the count of prefixSum in the map.
- Recurse on left and right children.
- Backtrack: decrement the count of prefixSum before returning.
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> prefixCount = new HashMap<>();
prefixCount.put(0L, 1); // base case: empty path
return dfs(root, 0L, targetSum, prefixCount);
}
private int dfs(TreeNode node, long prefixSum, int target,
Map<Long, Integer> prefixCount) {
if (node == null) return 0;
prefixSum += node.val;
// how many times (prefixSum - target) appeared earlier on this path
int count = prefixCount.getOrDefault(prefixSum - target, 0);
// record current prefix sum
prefixCount.merge(prefixSum, 1, Integer::sum);
count += dfs(node.left, prefixSum, target, prefixCount);
count += dfs(node.right, prefixSum, target, prefixCount);
// backtrack — remove current prefix sum contribution
prefixCount.merge(prefixSum, -1, Integer::sum);
return count;
}
Use long for prefixSum to avoid integer overflow when node values and the tree depth are large.
- Time: O(n) — each node is visited exactly once; HashMap operations are O(1) average.
- Space: O(n) — the HashMap stores at most O(h) entries at any point (h = tree height),
but O(n) in total across the full traversal due to backtracking. Recursion stack is O(h).