Maximum Binary Tree
You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
- Create a root node whose value is the maximum value in
nums. - Recursively build the left subtree on the subarray prefix to the left of the maximum value.
- Recursively build the right subtree on the subarray suffix to the right of the maximum value.
Return the maximum binary tree built from nums.
Example 1
6
/ \
3 5
\ /
2 0
\
1Input
nums = [3,2,1,6,0,5]Output
[6,3,5,null,2,0,null,null,1]The largest value is 6, with left prefix [3, 2, 1] forming the left subtree and right suffix [0, 5] forming the right subtree recursively.
Example 2
3
\
2
\
1Input
nums = [3,2,1]Output
[3,null,2,null,1]The maximum value 3 becomes the root, and the remaining suffix [2, 1] recursively forms the right-skewed subtree.
Constraints
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
- All integers in
numsare unique.