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

短命女 2023-10-08 16:13 1阅读 0赞

## 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;
        }
    }