UVa 536

From Algorithmist
Jump to navigation Jump to search

536 - Tree Recovery[edit]

  • Problem link -> [1]

Summary[edit]

Given Preorder and inorder traversed string. We need to find postorder traversal string

Explanation[edit]

Just need to construct the tree from the preorder and inorder string. and then get the postorder traversal string

Implementations[edit]

#include<iostream>
#include<string>
using namespace std;
struct node
{
       char info;
       node *left;
       node *right;     
};
long long pre;
node* construct_tree(string preorder, string inorder,int inStart, int inFinal)
{
     if(inStart>inFinal)
     {
         return NULL;
     }
     long long i,inIndex;
     node *temp=new node;
     temp->info=preorder[pre++];
     for(i=inStart;i<=inFinal;i++)
     {
          if(inorder[i]==temp->info)
          {
               inIndex=i;                            
          }                            
     }
     temp->left=construct_tree(preorder,inorder,inStart,inIndex-1); 
     temp->right=construct_tree(preorder,inorder,inIndex+1,inFinal);
     return temp;
}

void postorder_traversal(node *r)
{
     if(r==NULL)
          return;
     postorder_traversal(r->left);     
     
     postorder_traversal(r->right); 
     cout<<r->info;    
}
int main()
{
    
    string preorder,inorder,postorder;
    while(cin>>preorder>>inorder)
    {
          long long len_in=inorder.length();
          pre=0;                      
          node *root=construct_tree(preorder,inorder,0,len_in-1); 
          postorder_traversal(root); 
          cout<<endl;                         
    }
    
    return 0;
}

Input[edit]

DBACEGF ABCDEFG
BCAD CBAD

Output[edit]

ACBFGED
CDAB

Solutions[edit]

Categories here, use the form [[Category:UVa Online Judge|536]] [[Category: Category Name]], see Categories for a list