2021-03-13 | 654. 最大二叉树

ゝ一世哀愁。 2022-11-12 01:47 128阅读 0赞

### 1. 题目描述 ###

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

1.  二叉树的根是数组 `nums` 中的最大元素。
2.  左子树是通过数组中 **最大值左边部分** 递归构造出的最大二叉树。
3.  右子树是通过数组中 **最大值右边部分** 递归构造出的最大二叉树。

返回有给定数组 `nums` 构建的 **最大二叉树**。

**示例 1：**  
![在这里插入图片描述][20210321215905271.jpg]

输入：nums = [3,2,1,6,0,5]
    输出：[6,3,5,null,2,0,null,null,1]
    解释：递归调用如下所示：
    - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
        - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
            - 空数组，无子节点。
            - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
                - 空数组，无子节点。
                - 只有一个元素，所以子节点是一个值为 1 的节点。
        - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
            - 只有一个元素，所以子节点是一个值为 0 的节点。
            - 空数组，无子节点。

**示例 2：**  
![在这里插入图片描述][20210321215935783.jpg]

输入：nums = [3,2,1]
    输出：[3,null,2,null,1]

**提示：**

*  `1 <= nums.length <= 1000`
 *  `0 <= nums[i] <= 1000`
 *  `nums` 中的所有整数 **互不相同**

### 2. 解题思路 ###

这道题目我们直接使用递归来实现：

*  首先获取到数组中最大的值，来作为当前的根节点
 *  分别获取数组中最大值的左边的数组元素和右边的数组元素
 *  使用两个数组分别进行递归构建二叉树的左右子树

**复杂度分析：**

*  时间复杂度：O(n)，一共递归了 n 次。每次递归寻找根节点时，需要遍历当前索引范围内所有元素找出最大值。一般情况下，每次遍历的复杂度为 O(logn)，总复杂度为 O(nlogn)。最坏的情况下，数组 nums 有序，总的复杂度为 O(n)
 *  空间复杂度：O(n)。递归调用深度为 n。平均情况下，长度为 n 的数组递归调用深度为 O(logn)。

### 3. 代码实现 ###

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

### 4. 提交结果 ###

![在这里插入图片描述][20210321215948871.png]

[20210321215905271.jpg]: /images/20221022/c484911221d94e61818b603f3700a8a1.png?
[20210321215935783.jpg]: https://img-blog.csdnimg.cn/20210321215935783.jpg
[20210321215948871.png]: https://img-blog.csdnimg.cn/20210321215948871.png?