654. Maximum Binary Tree
Medium
30 Points
Array
Divide and Conquer
Stack
Tree
Monotonic Stack
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:
Return the maximum binary tree built from nums.
Examples
Example 1
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
- The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
- Empty array, so no child.
- The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
- Empty array, so no child.
- Only one element, so child is a node with value 1.
- The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
- Only one element, so child is a node with value 0.
- Empty array, so no child.
Example 2
Input: nums = [3,2,1]
Output: [3,null,2,null,1]
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 1000All integers in nums are unique.
654. Maximum Binary Tree
Medium
30 Points
Array
Divide and Conquer
Stack
Tree
Monotonic Stack
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:
Return the maximum binary tree built from nums.
Examples
Example 1
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
- The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
- Empty array, so no child.
- The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
- Empty array, so no child.
- Only one element, so child is a node with value 1.
- The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
- Only one element, so child is a node with value 0.
- Empty array, so no child.
Example 2
Input: nums = [3,2,1]
Output: [3,null,2,null,1]
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 1000All integers in nums are unique.