题目描述
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
示例 ：
输入： [3,2,1,6,0,5]
输出： 返回下面这棵树的根节点：
6
/ \ 3 5
\ /
2 0
\ 1
提示：
- 给定的数组的大小在 [1, 1000] 之间。
来源：LeetCode
思路
左右子树也是一棵最大二叉树，所以很容易就能想到递归。先找到数组中最大的元素，然后左右拆分成两个数组，左边生成左子树，右边生成右子树。递归的边界是nums为空数组，此时的节点应该是null。即可解决。
解法
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
const findMaxIndex = nums => {
let result = 0;
let max = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] > max) {
result = i;
max = nums[i];
}
}
return result;
};
/**
* @param {number[]} nums
* @return {TreeNode}
*/
const constructMaximumBinaryTree = nums => {
if (nums.length === 0) return null;
const maxIndex = findMaxIndex(nums);
const leftArr = nums.slice(0, maxIndex);
const rightArr = nums.slice(maxIndex + 1);
const root = new TreeNode(nums[maxIndex]);
root.left = constructMaximumBinaryTree(leftArr);
root.right = constructMaximumBinaryTree(rightArr);
return root;
};