460. Leaf Path Target
A hiker studies a trail map shaped like a binary tree stored in root. Each node holds the elevation change of that stretch of trail, and every trail ends at a leaf (a node with no children). The hiker is searching for a complete route from the trailhead to an end point whose total change equals target.
Return true if some path that starts at root, goes downward, and finishes at a leaf has node values adding up to exactly target; otherwise return false. A path that stops at a non-leaf node does not count. An empty tree has no such path, so return false.
Example 1
- Input:
- root = [5,3,8,1,null,2,6], target = 15
- Output:
- true
- Explanation:
The path 5, 8, 2 ends at a leaf and sums to 15.
Example 2
- Input:
- root = [5,3,8,1,null,2,6], target = 14
- Output:
- false
- Explanation:
The leaf paths sum to 9, 15 and 19, so none reaches 14.
Example 3
- Input:
- root = [4,-2,null,7], target = 9
- Output:
- true
- Explanation:
The path 4, -2, 7 ends at a leaf and sums to 9.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node value ≤ 1000
-109 ≤ target ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)