Advertisement
prakharvk

contruct full binary tree from preorder and postorder traversals

Jun 16th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. int search(int post[],int x, int start, int end){
  2.     int index=-1;
  3.     for(int i=start;i<end;i++){
  4.         if(post[i]==x){
  5.             return i;
  6.         }
  7.     }
  8.     return index;
  9. }
  10. Node* buildTree(int pre[], int post[], int preS, int preE,int posS, int posE){
  11.     if(preS>preE){
  12.         return NULL;
  13.     }
  14.    
  15.     if(preS==preE){
  16.         return pre[preS];
  17.     }
  18.     int index=search(post,posS,posE,pre[preS]);
  19.     int preLS=preS+1;
  20.     int preLE=postLE-postLS+preLS;
  21.     int preRS=preLE+1;
  22.     int preRE=preE;
  23.     int postLS=posS;
  24.     int postLE=index;
  25.     int postRS=index+1;
  26.     int postRE=posE-1;
  27.     Node *root=new newNode(pre[preS]);
  28.     root->left=buildTree(pre,post,preLS,preLE,postLS,postLE);
  29.     root->right=buildTree(pre,post,preRS,preRE,postRS,postRE);
  30.     return root;
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement