给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建: 1.创建一个根节点,其值为nums中的最大值。 2.递归地在最大值左边的子数组前缀上构建左子树。3.递归地在最大值右边的子数组后缀上构建右子树。返回num5构建的最大二叉树。
输入:nums = [3,2,1,6,0,5] 输出:[6,3,5,null,2,0,null,null,1] 解释:递归调用如下所示:
题目示例来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/maximum-binary-tree
1 <= nums.length <= 1000 0 <= nums[i] <= 1000 nums 中的所有整数 互不相同
方法一:递归 本方法非常简单。创建方法construct(nums,1,r),用于找出在数组nums中从l到,索引(不包含第,个位置)中最大二叉树的根节点。 算法步骤如下:
复杂度分析 . 时间复杂度:o(n²)。方法construct—共被调用n次。每次递归寻找根节点时,需要遍历当前索引范围内所有元素找出最大值。一般情况下,每次遍历的复杂度为O(log n),总复杂度为o(n logn)。最坏的情况下,数组Tums有序,总的复杂度为O(n²)。 . 空间复杂度:O(n)。递归调用深度为n。平均情况下,长度为n的数组递归调用深度为O(log n)。
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;
}
}