529. Tallest-Root Tree
A tournament organiser lists the strengths of the entrants in nums in the order they signed up, and wants to build a bracket tree from them: the strongest entrant becomes the root, the entrants who signed up before the strongest form the left subtree and those who signed up after form the right subtree, and each part is built again by the same rule.
Return the root of the resulting binary tree. All strengths are distinct, so the shape is unique. For an empty array return an empty tree.
Example 1
- Input:
- nums = [4,10,2,7,5]
- Output:
- [10,4,7,null,null,2,5]
- Explanation:
10 is the largest so it is the root; [4] forms its left subtree and [2, 7, 5] its right subtree, whose root is 7 with children 2 and 5.
Example 2
- Input:
- nums = [8,1,6]
- Output:
- [8,null,6,1]
- Explanation:
8 is the root with nothing before it; the right part [1, 6] has root 6 with left child 1.
Constraints
0 ≤ nums.length ≤ 1000
-106 ≤ nums[i] ≤ 106
All values are distinct
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(n)