Maximum Binary Tree

给一个数组, 求返回mbt, 定义mbt是

1. Create a root node whose value is the maximum value in nums.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

这个题直接找max的index就可以.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums == null || nums.length == 0)
            return null;
        return constructMaximumBinaryTree(nums, 0, nums.length - 1);
    }
    private TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
        if(start > end)
            return null;
        int mid = getMaxIndex(nums, start, end);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = constructMaximumBinaryTree(nums, start, mid - 1);
        root.right = constructMaximumBinaryTree(nums, mid + 1, end);
        return root;
    }
    
    private int getMaxIndex(int[] nums, int start, int end){
        int maxIndex = Integer.MIN_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = start; i <= end; i++) {
            if(nums[i] > max){
                max = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}