Path Sum

Tree
DFS

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 node values equals targetSum.

Examples

Example 1

Input

root

target22

Output

true

Example 2

Input

root

target5

Output

false

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
-1000 ≤ Node.val ≤ 1000
-10⁷ ≤ target ≤ 10⁷

Stuck? Hint 1

DFS carrying the remaining sum: subtract the current node value on the way down.

Input

target22

Expected Output

true

Ctrl / ⌘ + Enter

Path Sum

Tree
DFS

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 node values equals targetSum.

Examples

Example 1

Input

root

target22

Output

true

Example 2

Input

root

target5

Output

false

Constraints

The number of nodes in the tree is in the range [0, 10⁴].
-1000 ≤ Node.val ≤ 1000
-10⁷ ≤ target ≤ 10⁷

Stuck? Hint 1

DFS carrying the remaining sum: subtract the current node value on the way down.

Input

target22

Expected Output

true

Ctrl / ⌘ + Enter