#654
Maximum Binary Tree
pupil · 385 · lc medium +24 · verified · 86.3% accepted · 5,419 likes · top 97%
Description
Given an integer array nums with no duplicates, build a "maximum binary tree" as follows: the root is the largest element of nums; the left subtree is the maximum binary tree of the elements to the left of that maximum; the right subtree is the maximum binary tree of the elements to the right. Return the resulting tree.
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]
Code
1
2
3
4
5
6
7
8
9