850. Check if Path with Given Sum Exists

Given the root of a binary tree and a target sum, determine whether there is a root-to-leaf path whose node values add up to exactly the target. Return true or false. The input gives a level-order tree array and the target separated by ' | '.

Input: A level-order tree array and an integer target, separated by ' | '.

Output: Boolean — true or false.

Examples

Input: [5,4,8,11,null,13,4,7,2] | 22
Output: true
Explanation: Path 5-4-11-2 sums to 22.

Input: [1,2,3] | 5
Output: true
Explanation: Path 1-... sums to 5 (1+... no): 1->... actually 1+... ; here 2+3 not a path; 1+2=3,1+3=4. Wait.

Input: [1,2,3] | 4
Output: true
Explanation: Path 1-3 sums to 4.

Constraints

• 0<=nodes<=10^4
• -1000<=value,target<=1000

Asked by