LeetCode75-437-Path-Sum-III

🧠 Summary of Thoughts

Method 1

For every node in the tree, treat it as a starting point, and count how many downward paths from that node sum to the target.

So the problem is divided into two parts:

1. A function that counts valid paths starting from the current node
2. Recursively apply this logic to every node in the tree

For every node, I recursively count the number of downward paths starting from that node that sum to the target. Since each node may re-traverse its subtree, the worst case time complexity is O(n²).

Method 2: Prefix

• Use HashMap to store the prefix, and if there exist currSum - target, which means we find the values sum equals to target.
• Backtrack is important!

Code（Java）

1. Time Complexity: O(n²)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        return countFun(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }
    private int countFun(TreeNode node, long target) {
        if (node == null) {
            return 0;
        }
        int count = 0;
        if (node.val == target) {
            count++;
        }
        count += countFun(node.left, target - node.val);
        count += countFun(node.right, target - node.val);
        return count;
    }
}

2. O(n)

Using Prefix Sum, don’t forget to backtrack!

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixMap = new HashMap<>();
        prefixMap.put(0L, 1);
        return dfs(root, 0, targetSum, prefixMap);
    }
    private int dfs(TreeNode node, long currSum, int target, Map<Long, Integer> map) {
        if (node == null) {
            return 0;
        }
        currSum += node.val;
        int count = map.getOrDefault(currSum - target, 0);
        map.put(currSum, map.getOrDefault(currSum, 0) + 1);
        count += dfs(node.left, currSum, target, map);
        count += dfs(node.right, currSum, target, map);
        // Backtrack
        map.put(currSum, map.get(currSum) - 1);

        return count;
    }
}