469. Every Leaf Route
A hiking park describes its trails as a binary tree rooted at root: each node is a signpost carrying a number, and each leaf (a signpost with no onward trail) is a trailhead end. The ranger wants every complete route from the entrance root down to a leaf, written as the signpost numbers joined by ->, for example 3->-2->7.
Return the routes as an array of strings, ordered by the left-to-right position of their final leaf. Negative numbers keep their minus sign. A tree with only a root gives that single value as one route, and an empty tree gives an empty array.
Example 1
- Input:
- root = [6,3,8,null,5,null,-1]
- Output:
- ["6->3->5","6->8->-1"]
- Explanation:
Reading left to right, the first route ends at leaf 5 and the second at leaf -1.
Example 2
- Input:
- root = [2,-7,null,4,9]
- Output:
- ["2->-7->4","2->-7->9"]
- Explanation:
Node -7 is the only child of 2 and has two leaves, 4 then 9.
Constraints
0 ≤ number of nodes in root ≤ 1000
-100 ≤ Node.val ≤ 100
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 * h)
- Space
- O(n * h)