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

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

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

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

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    int findMax(const vector<int>& nums,int a,int b){
        if(a==b)return a;
        int max = a;
        for(int i = a+1; i < b; i ++){
            max = nums[max] < nums[i] ? i : max;
        }
        return max;
    }
    TreeNode* constructMaximumBinaryTree(const vector<int>& nums) {
        return makeMaxBiTree(nums,0,nums.size());
    }
    
    TreeNode* makeMaxBiTree(const vector<int>& nums, int begin, int end){
        if(begin>=end) return NULL;
        int max = findMax(nums,begin,end);
        TreeNode * p = new TreeNode(nums[max]);
        p->left = makeMaxBiTree(nums,begin,max);
        p->right = makeMaxBiTree(nums,max+1,end);
        return p;
    }
    

};