Easy

Path Sum

019

Given a binary tree encoded as level-order with -100000 as null and targetSum, return true if a root-to-leaf path sums to targetSum.

EXAMPLES

Example 1

Input
{
  "root": [
    5,
    4,
    8,
    11,
    -100000,
    13,
    4,
    7,
    2,
    -100000,
    -100000,
    -100000,
    1
  ],
  "targetSum": 22
}

Output
true

FUNCTION SHAPE

root: intArraytargetSum: int→bool

SOLUTION NOTE

Track cumulative value as we traverse. We subtract from target rather than adding up - this simplifies the leaf check!

Reveal reference solution +

pythonREFERENCE

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

    return (self.hasPathSum(root.left, targetSum - root.val) or
            self.hasPathSum(root.right, targetSum - root.val))

TimeO(n)

SpaceO(h)

Open on LeetCode ↗