1 题目描述
给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建:
1.创建一个根节点，其值为nums中的最大值。
2.递归地在最大值左边的子数组前缀上构建左子树。3.递归地在最大值右边的子数组后缀上构建右子树。返回num5构建的最大二叉树。
2 题目示例
输入：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 的节点。
- 空数组，无子节点。
题目示例来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-binary-tree
3 题目提示
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同
4 思路
方法一:递归
本方法非常简单。创建方法construct(nums，1，r)，用于找出在数组nums中从l到，索引(不包含第，个位置)中最大二叉树的根节点。
算法步骤如下:
- 首先调用construct(nums，0, n)，其中n是数组nums
的长度。
- 在索引范围(l : r―1)内找到最大值的索引，将nums[max_司]作为根节点。
- 调用construct(nums,1，max_i)创建根节点的左孩子。递归执行此操作，创建根节点的整个左子树。
- 类似的，调用construct(nums,max_i + 1，r)创建根节点的右子树。
- 方法construct(nums,0, n)返回最大二叉树的根节点。
复杂度分析
. 时间复杂度:o(n²)。方法construct—共被调用n次。每次递归寻找根节点时，需要遍历当前索引范围内所有元素找出最大值。一般情况下，每次遍历的复杂度为O(log n)，总复杂度为o(n logn)。最坏的情况下，数组Tums有序，总的复杂度为O(n²)。
. 空间复杂度:O(n)。递归调用深度为n。平均情况下，长度为n的数组递归调用深度为O(log n)。
5 我的答案
public class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return construct(nums, 0, nums.length);
}
public TreeNode construct(int[] nums, int l, int r) {
if (l == r)
return null;
int max_i = max(nums, l, r);
TreeNode root = new TreeNode(nums[max_i]);
root.left = construct(nums, l, max_i);
root.right = construct(nums, max_i + 1, r);
return root;
}
public int max(int[] nums, int l, int r) {
int max_i = l;
for (int i = l; i < r; i++) {
if (nums[max_i] < nums[i])
max_i = i;
}
return max_i;
}
}