LeetCode - 最大二叉树

LeetCode第654题，难度中等。可能后面的题都比较水吧....

原题地址：https://leetcode-cn.com/problems/maximum-binary-tree/

题目描述：

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

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

提示：

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/maximum-binary-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

首先找到数组中最大的值和对应的索引，然后建立一颗树，将左子树设定为该索引左侧的数组构建的最大二叉树，右子树设定为右侧数组构建的最大二叉树。

其实这样子挺慢的，毕竟需要遍历好多次。如果有更好的方法，请告诉我。

中文官网题解：

https://leetcode-cn.com/problems/maximum-binary-tree/solution/

个人题解：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int index = 0;
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        TreeNode root = new TreeNode(max);
        if (index != 0) {
            root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, index));
        }
        if (index < nums.length) {
            root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, index + 1, nums.length));
        }
        return root;
    }
}

结果：

默默的又是100%。