二叉树——654. 最大二叉树

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到，索引(不包含第，个位置)中最大二叉树的根节点。
算法步骤如下:

1. 首先调用construct(nums，0, n)，其中n是数组nums
   的长度。
2. 在索引范围(l : r―1)内找到最大值的索引，将nums[max_司]作为根节点。
3. 调用construct(nums,1，max_i)创建根节点的左孩子。递归执行此操作，创建根节点的整个左子树。
4. 类似的，调用construct(nums,max_i + 1，r)创建根节点的右子树。
5. 方法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;
    }
}