LeetCode/654. 最大二叉树

654. 最大二叉树

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

1. 二叉树的根是数组中的最大元素。
2. 左子树是通过数组中最大值左边部分构造出的最大二叉树。
3. 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例:

输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题其实很好想，我们首先明确需要干什么。首先需要找出这个数组中最大的值，记录这个最大值和最大值所在的索引，让这个最大值成为树的根节点。然后就是递归的生成左子树和右子树，分别对应数组中最大值左边的值和右边的值。最后返回这棵树即可。

具体代码如下：

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    TreeNode build(int[] nums, int left, int right) {
      	//结束条件
        if (left > right) return null;

      	//初始化最大值和最大值所在索引
        int index = -1;
        int largest = Integer.MIN_VALUE;
      	//循环遍历数组，找出该区间中的最大值和最大值索引
        for (int i = left; i <= right; i++) {
            if (nums[i] > largest) {
                index = i;
                largest = nums[i];
            }
        }

      	//利用当前区间中的最大值生成根节点
        TreeNode node = new TreeNode(largest);
      	//递归生成左子树和右子树
        node.left = build(nums, left, index - 1);
        node.right = build(nums, index + 1, right);

      	//返回该树即可
        return node;
    }
}