0437.md

437. Path Sum III

Level:

Topic:

Question

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.

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.\

Intuition

Recursive: Use hashmap to store the presum of each subpath and its frequency \

Code

Time: O(n)
Space: O(n)

Recursive

// backtrack
HashMap<Integer, Integer> preSum = new HashMap<>();
int targetSum;
int pathSum;
public int pathSum(TreeNode root, int targetSum) {
    this.preSum.put(0, 1);
    this.targetSum = targetSum;
    this.pathSum = 0;
    return helper(root);
}

private int helper(TreeNode root) {
    if (root == null)
        return 0;

    pathSum += root.val;
    int ans = preSum.getOrDefault(pathSum-targetSum, 0);
    preSum.put(pathSum, preSum.getOrDefault(pathSum, 0)+1);

    ans += helper(root.left) + helper(root.right);

    preSum.put(pathSum, preSum.get(pathSum)-1);
    pathSum -= root.val;

    return ans;
}