# My C++ solution with O(n) time and O(lgn) space

• ``````class Solution {
public:
void vector_cp(vector<int> in,vector<int> &out,int s,int t){
for(int i=s;i<=t;i++)
out.push_back(in[i]);
}
void Build(TreeNode* &root, vector<int>& inorder, vector<int>& postorder, int in_s, int in_t, int pos_s, int pos_t){
int size=inorder.size();
if(in_t<in_s)
return;
if(in_t==in_s){
root=new TreeNode(inorder[in_s]);
return;
}
int mid=postorder[pos_t];
int idx;
for(idx=in_t;idx>=in_s;idx--){
if(inorder[idx]==mid)
break;
}
root=new TreeNode(mid);
Build(root->left,inorder,postorder,in_s,idx-1,pos_s,idx-in_s+pos_s-1);
Build(root->right,inorder,postorder,idx+1,in_t,idx-in_s+pos_s,pos_t-1);
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
TreeNode *rs=NULL;
int size=inorder.size();
Build(rs,inorder,postorder,0,size-1,0,size-1);
return rs;
}
};
``````

• Recursion needs O(log n) space.

• @hwf Thank you for correction!

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