Root-to-Leaf Path Sum

L7 Medium Trees

Concept

A recursive traversal can carry a running target down the tree: subtract the current node's value, and check the remainder at each leaf.

Given the root of a binary tree and a targetSum, return true if there is a root-to-leaf path whose values add up to targetSum. A leaf is a node with no children.

Examples

▸ root = [5, 4, 8, 11, nil, 13, 4, 7, 2, nil, nil, nil, 1], targetSum = 22

→ true

▸ root = [1, 2], targetSum = 1

→ false

▸ root = [1, 2, 3], targetSum = 5

→ false

Progressive Hints

Hint 1 · Nudge

Subtract as you descend, and only judge the balance at the leaves.

Hint 2 · Plan

Recurse with the remaining target being targetSum minus the node's value. When you reach a leaf, the path is valid only when the remaining target equals the leaf's value.

Hint 3 · Approach

If root is nil, return false. If root is a leaf, return root.val == the remaining target. Otherwise recurse into either child with the remaining target reduced by root.val.

Output

// Run your code to see the output here.