100. Path Sum

Walk down from the root, subtracting each node's value from the remaining target. At a leaf, the path sums to the target exactly when the remaining amount equals the leaf's value. Any leaf that closes the gap makes the answer true.

Idea

Instead of accumulating a running sum, carry the remaining target down the tree, subtracting each node's value. Then a root-to-leaf path works exactly when, at a leaf, the leftover target equals that leaf's value. DFS short-circuits as soon as any qualifying leaf is found.

Algorithm

hasPathSum(node, target):

1. If node is null, return false (no path).
2. If node is a leaf, return target == node.val.
3. Otherwise recurse into both children with target - node.val; return true if either succeeds.

Worked example: target = 22, path 5 → 4 → 11 → 2

• 22 − 5 = 17 → 17 − 4 = 13 → 13 − 11 = 2 → leaf 2 with remaining 2 → match → true.

Complexity

• Time: O(n) — each node visited once.
• Space: O(h) recursion depth.

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        int remaining = targetSum - root.val;
        return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
    }
}