LeetCode 437. Path Sum III

Posted on In , Views:

šŸ§© Problem Description

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the node values in the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

šŸ’¬ Example

Example 1

1
2
3
4
5
6
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:
- 5 ā†’ 3
- 5 ā†’ 2 ā†’ 1
- -3 ā†’ 11

Example 2

1
2
Input: root = [1], targetSum = 1
Output: 1

šŸ’” Approach 1: DFS (Brute Force)

The most straightforward solution is:

  • For each node, start a DFS to find all downward paths whose sum equals targetSum.
  • This results in O(nĀ²) time complexity in the worst case.

šŸ”¢ Java Code (Brute Force)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return countFromNode(root, targetSum) 
               + pathSum(root.left, targetSum) 
               + pathSum(root.right, targetSum);
    }

    private int countFromNode(TreeNode node, long targetSum) {
        if (node == null) return 0;
        int count = 0;
        if (node.val == targetSum) count++;
        count += countFromNode(node.left, targetSum - node.val);
        count += countFromNode(node.right, targetSum - node.val);
        return count;
    }
}

šŸ’” Approach 2: Prefix Sum + HashMap (Optimized)

We can reduce time complexity to O(n) by:

  • Maintaining a prefix sum map that stores (currentSum ā†’ frequency).
  • At each node, we calculate how many previous prefix sums satisfy:
    1
    currentSum - targetSum = somePreviousPrefix
  • Update the map during DFS and backtrack after visiting children.

šŸ”¢ Java Code (Optimized)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0L, 1); // Base case: sum = 0 occurs once
        return dfs(root, 0L, targetSum, prefixSumMap);
    }

    private int dfs(TreeNode node, long currSum, int targetSum, Map<Long, Integer> map) {
        if (node == null) return 0;

        currSum += node.val;
        int count = map.getOrDefault(currSum - targetSum, 0);

        map.put(currSum, map.getOrDefault(currSum, 0) + 1);

        count += dfs(node.left, currSum, targetSum, map);
        count += dfs(node.right, currSum, targetSum, map);

        map.put(currSum, map.get(currSum) - 1); // backtrack

        return count;
    }
}

ā± Time and Space Complexity

Brute Force

  • Time: O(nĀ²) in worst case
  • Space: O(h) recursion stack

Prefix Sum Optimized

  • Time: O(n) ā€” visiting each node once
  • Space: O(n) ā€” prefix sum map and recursion stack

āœļø Summary

  • Brute Force: Try all starting points ā†’ simple but slow.
  • Prefix Sum: Tracks how many ways we can reach targetSum efficiently.
  • Related problems:
    • lc-112 ā€” Path Sum
    • lc-113 ā€” Path Sum II
    • lc-437 ā€” Path Sum III (this one)