JAVA基础算法（11）----- 最大二叉树

​​​​​​

​ 最大二叉树 ​​
​

活动地址：CSDN21天学习挑战赛

一、题目

标题：最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

示例 1：

图 1.1

输入：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 的节点。
  - 空数组，无子节点。

示例 2：

图 1.2

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

二、解题

• 这个题目的要求是将一个数组中的最大元素作为一棵树的父辈结点，然后对剩余的数组进行拆分再进行选取下一层的结点元素，最终组成的是一个类似大根堆的二叉树；
• 根据题目要求我们还可以看出所传入的数组是一个中序遍历的数据集，也就是说在每一次进行拆分的时候只用找到作为父结点元素的位置即可确定其左右孩子的区间；

2.1 确定作为当前位置结点的元素在数组的位置

• 首先我们要建立一个辅助变量存储的值为数组的初始坐标；
• 对整个数组进行遍历对比，将最大元素位置的坐标传入辅助变量；
• 我们定义一个结点，并将所取得的最大数据值传入该结点的数据域；

图 2.1

2.2 拆分数组

• 声明两个变量用于存储左右两个区间的数据元素的个数；
• 因为数组的存储的从 0 开始的所以左区间的范围为 0 - 当前结点坐标位置 - 1 ，即左区间的大小为当前结点坐标位置；
• 而右边区间要使用数组的最大长度减去当前结点坐标位置再减 1 ，因为使用数组长度作为被减数而不是最大坐标号，故需要多减去一个 1 ；
• 使用数组截取的功能将左右区间赋值到两个数组；（ 四个参数从左到右：所截取的数组、所截取数组的起始坐标号、所传入的数组、所传入的起始坐标、所传入的终点坐标<\i> ）

图 2.2

2.3 递归确定后续结点

• 在左右两边的数组确定之后进行递归，将左边数组的递归结果连接至左孩子结点，右边数组的递归结果连接至右孩子结点；
• 在方法的头部添加一个判断，如果当前传入的数组为空则代表为空，直接返回null；
• 在方法底部返回当前结点；

图 2.3

三、代码分享及力扣评分

3.1 力扣评分

• 执行用时 3 ms ，内存消耗在 41.2 ~ 41.6 MB ；

图 3.1

3.2 代码分享

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if( nums.length == 0 )
            return null;
        int max = 0;
        for( int i = 1; i < nums.length; i++)
            if( nums[max] < nums[i] )
             max = i;
        TreeNode node = new TreeNode( nums[max] );
        int leftLen = max;
        int rightLen = nums.length-max-1;
        int[] arr1 = new int[leftLen];
        int[] arr2 = new int[rightLen];
        System.arraycopy( nums , 0 , arr1 , 0 , leftLen );
        System.arraycopy( nums , max+1 , arr2 , 0 , rightLen );
        node.left = constructMaximumBinaryTree( arr1 );
        node.right = constructMaximumBinaryTree( arr2 );
        return node;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20