Path Sum

Intuition

Instead of accumulating a running total on the way down, we shrink the target by each node value we pass through. This reframes the question at every node as: does one of my subtrees contain a root-to-leaf path summing to the reduced target? A leaf answers directly by comparing its own value against what remains. Because the recursion only reports true when it actually reaches a leaf with an exact match, we never mistakenly count a partial path.

Algorithm walkthrough

1. 1If the current node is null, there is no path here, so return false.
2. 2If the node is a leaf, return whether the target equals the node's value.
3. 3Otherwise compute the remaining amount as target minus the node's value.
4. 4Recurse into the left and right children with this remaining amount.
5. 5Return true if either subtree reports a valid path; the answer bubbles up to the root.

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return targetSum == root.val
        remaining = targetSum - root.val
        return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)