5.27 Path Sum III

5.27.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 437
• Difficulty: Medium
• URL: https://leetcode.com/problems/lc-path-sum-iii/
• Tags:
• Techniques: Depth First Search, Tree, Prefix Sum

5.27.2 Description

Count the number of paths in a binary tree that sum to a target. Paths may start and end anywhere but must go downward.

5.27.3 Solution - Prefix Sum DFS

5.27.3.1 Walkthrough

Use DFS while tracking a running prefix sum and a hash map of prefix counts. For each node, check how many previous prefix sums equal currentSum - target. Update the map while exploring children and backtrack counts afterward.

5.27.3.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

5.27.3.3 Code - Java

public int pathSum(TreeNode root, int targetSum) {
    Map<Integer, Integer> prefix = new HashMap<>();
    prefix.put(0, 1);
    return dfs(root, 0, targetSum, prefix);
}

private int dfs(TreeNode node, int current, int target, Map<Integer, Integer> prefix) {
    if (node == null) {
        return 0;
    }

    current += node.val;
    int count = prefix.getOrDefault(current - target, 0);
    prefix.put(current, prefix.getOrDefault(current, 0) + 1);

    count += dfs(node.left, current, target, prefix);
    count += dfs(node.right, current, target, prefix);

    prefix.put(current, prefix.get(current) - 1);
    return count;
}