624.最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

解答

1. 递归

对于每个根节点，只需要找到当前nums的最大值和对应的索引，然后递归调用左右数组构建左右子树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var constructMaximumBinaryTree = function(nums) {
    if(!nums.length) return null
    let maxVal = Math.max(...nums),maxIndex = nums.indexOf(maxVal)
    const root = new TreeNode(maxVal)
    root.left = constructMaximumBinaryTree(nums.slice(0,maxIndex))
    root.right = constructMaximumBinaryTree(nums.slice(maxIndex+1))
    return root
};