You are given an integer array nums
with no duplicates. A maximum binary tree can be built recursively from nums
using the following algorithm:
nums
.Return the maximum binary tree built from nums
.
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 <= 1000
0 <= nums[i] <= 1000
nums
are unique.soluiton
这道题目也是一个构建的问题。 思想也是递归的形式去找 就是每次找到最大值的位置,为分割点,左右来建立数组
var constructMaximumBinaryTree = function(nums) {
return dfs(0,nums.length-1,nums);
};
function dfs( l, r, nums){
if(l > r) return null;
let max_index = get_MAX_index(nums,l,r);
let node = new TreeNode(nums[max_index]);
node.left = dfs(l,max_index-1,nums);
node.right = dfs(max_index+1,r,nums);
return node;
}
//找到 l 和 r 区间的最大值,返回下标
function get_MAX_index(nums,l,r){
let max_index= -1;
let max_int = -1;
for(let i = l; i<=r;i++){
if(nums[i]>max_int){
max_int = nums[i];
max_index = i;
}
}
return max_index;
}