654.最大二叉树

灰太狼 2023-10-16 10:24 42阅读 0赞

#### 654.最大二叉树 ####

*  题干描述
 *  解题思路
 *   *  1. 确定递归函数的参数和返回值
     *  2. 确定终止条件
     *  3. 确定单层递归的逻辑
     *   *  3.1. 找到最大者和下标来构造根节点并分割数组
         *  3.2. 最大值所在的下标左区间构造左子树
         *  3.3. 最大值所在的下标右区间构造右子树
 *  优化思路
 *  不同风格的实现
 *  代码实现

## 题干描述 ##

[654.最大二叉树-力扣入口][654._-]

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

二叉树的根是数组中的最大元素。  
左子树是通过数组中最大值左边部分构造出的最大二叉树。  
右子树是通过数组中最大值右边部分构造出的最大二叉树。  
通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ：  
![在这里插入图片描述][7891a9696b4f4cd595d9ff54ed08bf1d.png]  
提示：

给定的数组的大小在 \[1, 1000\] 之间。

## 解题思路 ##

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

### 1. 确定递归函数的参数和返回值 ###

参数传入的是存放元素的数组，返回该数组构造的二叉树的头节点。

### 2. 确定终止条件 ###

题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。

那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，返回这个节点。这表示一个数组大小是1的时候，构造了一个新的节点，并返回。

### 3. 确定单层递归的逻辑 ###

#### 3.1. 找到最大者和下标来构造根节点并分割数组 ####

先要找到数组中最大的值和对应的下标，最大的值构造根节点，下标用来下一步分割数组。

#### 3.2. 最大值所在的下标左区间构造左子树 ####

这里要判断maxValueIndex>0，因为要保证左区间至少有一个数值。

#### 3.3. 最大值所在的下标右区间构造右子树 ####

判断maxValueIndex<(nums.size()-1)，确保右区间至少有一个数值。

## 优化思路 ##

每次分隔不用定义新的数组，而是通过下标索引直接在原数组上操作。这样可以节约时间和空间上的开销。

## 不同风格的实现 ##

一般情况来说，如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下，终止条件也会相应的调整。

## 代码实现 ##

// 654.最大二叉树
    public TreeNode constructMaximumBinaryTree(int[] nums){
        
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }
    
    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex){
        
        if(rightIndex - leftIndex < 1){
         // 没有元素了
            return null;
        }
        if(rightIndex - leftIndex == 1){
         // 只有一个元素
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex; // 最大值所在位置
        int maxVal = nums[maxIndex]; // 最大值
        for(int i = leftIndex + 1; i < rightIndex; i++){
        
            if(nums[i] > maxVal){
        
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // 根据maxIndex划分左右子树
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }

**参考资料**：[代码随想录-654.最大二叉树][-654.]

[654._-]: https://leetcode.cn/problems/maximum-binary-tree/
[7891a9696b4f4cd595d9ff54ed08bf1d.png]: https://img-blog.csdnimg.cn/7891a9696b4f4cd595d9ff54ed08bf1d.png
[-654.]: https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE