Problem #112: Path Sum

Intuition & Strategy Breakdown

Perform DFS from root to leaf, subtracting node value from targetSum. Return true if reaching a leaf node where targetSum == node.val.

Python Solution

def hasPathSum(root, targetSum):
    if not root:
        return False

    targetSum -= root.val

    if not root.left and not root.right:
        return targetSum == 0

    return (hasPathSum(root.left, targetSum) or
            hasPathSum(root.right, targetSum))

Java Solution

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