C++ O(n) recursive solution


  • 0
    J
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        	if(nums.empty()) return NULL;
        	int m=INT_MIN,idx=0;
        	for(int i=0;i<nums.size();i++) {
        		if(nums[i]>m){
        			m=nums[i];
        			idx=i;
        		}
        	}
        	TreeNode * root = new TreeNode(m);
        	vector<int> left,right;
        	if(idx!=0){
        		left.assign(nums.begin(),nums.begin()+idx);
        		root->left = constructMaximumBinaryTree(left);
        	}
        	if(idx!=nums.size()-1){
        		right.assign(nums.begin()+idx+1,nums.end());
        		root->right = constructMaximumBinaryTree(right);
        	}
        	return root;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.