Description
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.
Examples
Input:
root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22Output:
trueExplanation:
5+4+11+2=22.
Input:
root = [1,2,3], targetSum = 5Output:
falseExplanation:
Root-to-leaf paths are 1->2 (sum=3) and 1->3 (sum=4). Neither equals 5.
Input:
root = [1,2], targetSum = 1Output:
falseExplanation:
The tree has root value 1, but the only root-to-leaf path is 1->2 with sum 3, which does not equal the target sum of 1. A leaf node must be reached, so stopping at the root (even though it equals targetSum) does not count.
Constraints
- •
0 ≤ nodes ≤ 5000