1. 题目描述

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

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

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

示例 1：
654. 最大二叉树 - 图1**

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

示例 2：
654. 最大二叉树 - 图2

  1. 输入：nums = [3,2,1]
  2. 输出：[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. 代码实现

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val, left, right) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.left = (left===undefined ? null : left)
    6. *     this.right = (right===undefined ? null : right)
    7. * }
    8. */
    9. /**
    10. * @param {number[]} nums
    11. * @return {TreeNode}
    12. */
    13. var constructMaximumBinaryTree = function(nums) {
    14.   if(nums.length === 0){
    15.       return null
    16.   }
    18.   let max = Math.max(...nums)
    19.   let root = new TreeNode(max)
    20.   let leftArray = nums.slice(0, nums.indexOf(max))
    21.   let rightArray = nums.slice(nums.indexOf(max) + 1)
    23.   root.left = constructMaximumBinaryTree(leftArray)
    24.   root.right = constructMaximumBinaryTree(rightArray)
    26.   return root
    27. };

    4. 提交结果

    image.png