Path Sum

Easy·Tagstreedfsrecursion

Problem Statement

Given the `root` of a binary tree and an integer `targetSum`, return `true` if the tree has a root-to-leaf path such that adding up all the values along the path equals `targetSum`. A leaf is a node with no children. Note: Assume a standard `TreeNode` class is already provided in the execution environment, containing `val`, `left`, and `right` properties.

Examples

Example 1

Input

root: [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum: 22

Tree

Output

"true"

Why

The root-to-leaf path 5 -> 4 -> 11 -> 2 has a sum of 5 + 4 + 11 + 2 = 22.

Example 2

Input

root: [1, 2, 3], targetSum: 5

Tree

Output

"false"

Why

There are two root-to-leaf paths in the tree: (1 -> 2) with sum 3, and (1 -> 3) with sum 4. Neither equals 5.

Example 3

Input

root: [], targetSum: 0

Output

"false"

Why

Since the tree is empty, there are no root-to-leaf paths.

Constraints

•The number of nodes in the tree is in the range [0, 5000].
•-1000 <= Node.val <= 1000
•-1000 <= targetSum <= 1000

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

This problem asks for a path from the root to a leaf. Depth-First Search (DFS) naturally explores complete paths one branch at a time.

Hint 2

Instead of keeping a running sum and passing it down, you can subtract the current node's value from `targetSum`. When you reach a leaf, you just check if `targetSum == node.val`!

Hint 3

What is your base case? If the current node is null, you should return `false`. If the node is a leaf (both left and right children are null), return whether its value equals the remaining sum.

Hint 4

If it's not a leaf, recursively call the function on the left and right children, passing down `targetSum - node.val`. Return `true` if EITHER the left child OR the right child returns `true`.