Untitled
plain_text
a month ago
1.3 kB
0
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); }