654. 最大二叉树

左闭右开，当左右指针相同时就终止递归

  1. class Solution {
  2. public:
  3.     unordered_map<int,int> map;
  4.     int getmax(int left,int right,vector<int> & nums)
  5.     {
  6.         int m = INT_MIN;
  7.         for(int i=left;i<right;i++)
  8.         {
  9.             if(nums[i]>m)m=nums[i];
  10.         }
  11.         return m;
  12.     }
  13.     TreeNode* traversal(int left, int right, vector<int>& nums)
  14.     { 
  15.         if(left>=right)return NULL;
  16.         int maxValue = getmax(left,right,nums);
  17.         TreeNode* root = new TreeNode(maxValue);
  18.         int maxIndex = map[maxValue];
  20.         root->left = traversal(left,maxIndex,nums);
  21.         root->right = traversal(maxIndex+1,right,nums);
  22.         return root;
  24.     }
  25.     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
  26.         if(nums.size()==0) return NULL;
  27.         for(int i=0;i<nums.size();i++)
  28.             map[nums[i]] = i;
  29.         return traversal(0,nums.size(), nums);
  30.     }
  31. };