473. All Target Routes
A hiking park is mapped as a binary tree. The trailhead is root, each junction splits into at most a left and a right trail, and a junction with no further trails is a lookout. Every junction carries an integer score, which may be negative, and the score of a route is the sum of the scores of all junctions on it, trailhead and lookout included.
Return every route that starts at root, ends at a lookout, and has a score exactly equal to target. Each route is a list of the junction values from the trailhead to the lookout. List the routes in the order a traversal meets them when it always explores the left trail before the right one. If no route matches, or the tree is empty, return an empty list.
Example 1
- Input:
- root = [7,3,9,2,5,4,null,1,null,null,null,8]target = 28
- Output:
- [[7,9,4,8]]
- Explanation:
Exactly one root-to-leaf route sums to 28, namely 7 -> 9 -> 4 -> 8.
Example 2
- Input:
- root = [6,2,4,5,null,3,5], target = 13
- Output:
- [[6,2,5],[6,4,3]]
- Explanation:
The routes 6 -> 2 -> 5 and 6 -> 4 -> 3 both end at leaves and sum to 13; the left route is listed first.
Example 3
- Input:
- root = [-3,4,-2,6,-5,8,null,2], target = 1000
- Output:
- []
- Explanation:
No root-to-leaf route sums to 1000, so the answer is an empty list.
Constraints
0 ≤ number of nodes ≤ 5000
-1000 ≤ Node.val ≤ 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,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n * h)
- Space
- O(n)