# Two C++ solution with explanation O(n)time O(1)space no recursion And O(n^2) recursion

• Solution 1:
The idea is we traverse from left to right. So if the current node->val more than the head->val we just put the head to the current node's left, because the current node aways at the right of the head. And then make the current node be the new head. we the current node->val is less than head, keep travel the right of head, right->right, right->right->right ......, when find a right node->val less than the current node->val, we put the current node to the right node's place and put the right node to the current node's left. But if all right node are all more than the current node, we need put the current node to the last right node 's right.

`````` //O(n) method
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size()==0)
return nullptr;
for(int i=1;i<nums.size();++i)
{
TreeNode *nowNode=new TreeNode(nums[i]);
{
}else
{
bool find=false;
while(rightNode->right)
{
if(nowNode->val>rightNode->right->val)
{
nowNode->left=rightNode->right;
rightNode->right=nowNode;
find=true;
break;
}else
rightNode=rightNode->right;
}
if(find==false)
rightNode->right=nowNode;
}
}
}
``````

Solution 2:
Easy to understand. just find the max num as the head, and do same to the left part and right part.

``````//O(n^2) method
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if(nums.size()==0)
return nullptr;
return helpBuildTree(nums,0,nums.size()-1);
}
TreeNode* helpBuildTree(vector<int>& nums,int left,int right) {
if(left>right)
return nullptr;
int maxIndex=left,maxNum=nums[left];
for(int i=left+1;i<=right;++i)
{
if(nums[i]>maxNum)
{
maxNum=nums[i];
maxIndex=i;
}
}
//cout<<maxNum<<" ";