1、前言

2、思路

此题的思路其实非常简单，主要是根据分治法将整个数组分开。

首先先想一个整体，我找到一个数组最大的数后，将这个节点变成一个父节点，然后最大数左边变成左子树，右边变成右子树，这不是妥妥的递归吗。然后思考一下 base case，肯定是分到数组最左边或者最右边的时候不能在分了（left > right），这时候返回 null 即可。

3、代码

public class MaxBinaryTree {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums == null){
            return null;
        }

        return helper(nums, 0, nums.length - 1);
    }

    private TreeNode helper(int[] nums, int left, int right){
        if(left > right){
            return null;
        }

        int maxIndex = findMax(nums, left, right);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = helper(nums, left, maxIndex - 1);
        root.right = helper(nums, maxIndex + 1, right);

        return root;
    }

    private int findMax(int[] nums, int left, int right){
        int max = Integer.MIN_VALUE;
        int index = -1;
        for(int i = left; i <= right; i++){
            if(nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        return index;
    }


    public static void main(String[] args) {
        int[] nums = {3,2,1,6,0,5};
        TreeNode root = new MaxBinaryTree().constructMaximumBinaryTree(nums);
        System.out.println();
    }
}