# Untitled

unknown
plain_text
a year ago
1.3 kB
1
Indexable
Never
```/************************************************************

Following is the TreeNode class structure

class TreeNode<T>
{
public:
T data;
TreeNode<T> *left;
TreeNode<T> *right;

TreeNode(T data)
{
this -> data = data;
left = NULL;
right = NULL;
}
};

************************************************************/

int findpos(int element,vector<int>&inOrder,int n){
for(int i=0;i<n;i++) {
if(inOrder[i]==element) return i;
}
return -1;
}

TreeNode<int>* solve(vector<int>& postOrder,vector<int>&inOrder,int &i,int s,int e,int n){
if(i<0 || s>e) return NULL;

int element=postOrder[i--];
int pos=findpos(element,inOrder,n);

TreeNode<int>* node =new TreeNode<int>(element);

node->right= solve(postOrder,inOrder,i,pos+1,e,n);  //why this order matters?
node->left = solve(postOrder,inOrder,i,s,pos-1,n);
return node;

}

TreeNode<int>* getTreeFromPostorderAndInorder(vector<int>& postOrder, vector<int>& inOrder){
int n=postOrder.size();
int postindex=n-1;
return solve(postOrder,inOrder,postindex,0,n-1,n);
}
```