146. Path Sum

Easy · Binary Tree

Given a binary tree and a target sum, determine if the tree has a root-to-leaf path where the sum of all node values equals the target sum. A leaf node is a node with no children.

You are given the tree as a level-order array where null represents a missing node. For example, [3, 9, 20, null, null, 15, 7] represents a tree where 3 is the root, 9 and 20 are its children, and 15 and 7 are children of 20.

Examples

Example 1
Input: tree = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
Output: true
Explanation: The tree has a root-to-leaf path [5, 4, 11, 2] that sums to 22.
Example 2
Input: tree = [1, 2, 3], targetSum = 5
Output: false
Explanation: The tree has two root-to-leaf paths: [1, 2] (sum = 3) and [1, 3] (sum = 4). Neither equals 5.

Constraints