654. 最大二叉树

题目描述

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

思路解析

对于二叉树类的问题，我们还是重复之前的思路：

1. 能否通过便遍历来解决
2. 能够通过递归来解决
3. 单独分离出一个节点，它需要做什么

思考完毕之后我们发现，可以通过递归来解决问题，每次都找出最大值来作为它的根节点，之后再对左子树和右子树分别递归来达到目的。

参考代码

var constructMaximumBinaryTree = function(nums) {
    if(nums.length===0) return null
    let max = Math.max.apply(null,nums)
    // js中获取索引，注意findIndex的使用方法
    let maxIndex = nums.findIndex(item=>{return item===max})
    // 将最大值作为根节点
    let root = new TreeNode(max)
    root.left = constructMaximumBinaryTree(nums.slice(0,maxIndex))
    root.right= constructMaximumBinaryTree(nums.slice(maxIndex+1))
    return root
};