给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。
输入:[3,2,1,6,0,5]
输出:返回下面这棵树的根节点:
6
/ \
3 5
\ /
2 0
\
1
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var constructMaximumBinaryTree = function(nums) {
if (nums.length === 0) {
return null;
}
let max = -1;
let maxIndex = -1;
for(let i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
maxIndex = i;
}
}
//寻找当前数组的最大值构造根节点
const root = new TreeNode(max);
console.log(max, maxIndex, nums.slice(0, maxIndex),nums.slice(maxIndex + 1));
// 用最大值的左右数组去构造子树
root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
return root;
};