UVA 536 Tree Recovery 建树+不建树

题意：

给出先序和中序，求后序。

思路：

①建树然后递归输出。

 //建树的

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 int n;

 char pre[],mid[];

 int judge[];

 struct node{

     char c;

     node *left,*right;

     node()

     {

         c='a';

         left=right=NULL;

     }

 };

 int cnt=,counter;

 node* build(node *root)

 {

     char c=pre[cnt++];//从a中取数 去b中查找

     int i;

     for( i=;i<n;i++)

     {

         if(mid[i]==c)

         break;

     }

     judge[i]=;

     root=new node();

     root->c=c;

     if(i>&&i<n&&judge[i-]!=)//在b数组中，如果一个数左相邻的数被标记，则不能向左建树

         root->left=build(root->left);

     if(i>=&&i<n-&&judge[i+]!=)//同样，在b数组中，如果一个数右相邻的数被标记，则不能向右建树

         root->right=build(root->right);

     return root;    //左右都建完，返回根结点

 }

 void postorder(node *root)

 {

     if(root->left)

     postorder(root->left);

     if(root->right)

     postorder(root->right);

     if(counter)

     //printf(" ");

     //counter++;

     printf("%c",root->c);

 }

 int main()

 {

     while(scanf("%s %s",pre,mid)==)

     {

         //printf("%s %s\n",pre,mid);

         counter = ;

         cnt = ;

         n=strlen(pre);

         memset(judge,,sizeof(judge));

         node *root = NULL;

         root = build(root);

         postorder(root);

         printf("\n");

     }

     return ;

 }

②不建树直接输出。

 //不建树

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 int n;

 char pre[],mid[];

 int cnt=,counter;

 void work(int left,int right)//左右端点

 {

     int i;

     char c=pre[cnt++];

     for(i=left;i<right;i++)

     {

         if(mid[i]==c)

         break;

     }

     if(i>left&&i<right)

     work(left,i);

     if(i>=left&&i<right-)

     work(i+,right);

     printf("%c",c);

 }

 int main()

 {

     while(scanf("%s %s",pre,mid)==)

     {

         //printf("%s %s\n",pre,mid);

         counter = ;

         cnt = ;

         n=strlen(pre);

         work(,n);

         printf("\n");

     }

     return ;

 }