leetcode 654

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

    TreeNode build(int[] nums, int low, int high){
        //base case
        if(low > high){
            return null;
        }
        //找到数组最大值并给root赋值
        int maxVal = Integer.MIN_VALUE;
        int index = -1;
        for (int i = low; i <= high; i++) {
            if(nums[i] > maxVal){
                maxVal = nums[i];
                index = i;
            }
        }
        //构造出树的根节点
        TreeNode root = new TreeNode(maxVal);
        root.left = build(nums, low, index - 1);
        root.right = build(nums, index + 1, high);
        return root;
    }
}