poj1741，poj 2255 Tree Recovery

2023-09-20 阅读 26 评论 0

摘要：#include <iostream> //给出先序和中序遍历序列,输出后序遍历序列#include <string.h>using namespace std;const int MAXLEN=100;void build(int len,char* s1,char* s2,char* s) //s1,s2和s都是在不断变化,所以s1[0]...也随之不同{if(len<=0)return

#include <iostream>        //给出先序和中序遍历序列,输出后序遍历序列
#include <string.h>
using namespace std;
const int MAXLEN=100;
void build(int len,char* s1,char* s2,char* s)    //s1,s2和s都是在不断变化,所以s1[0]...也随之不同
{
if(len<=0)
return;
    s[len-1]=s1[0];    //把根结点添加到最后
    int p=strchr(s2,s1[0])-s2;    //找到根结点在中序遍历中的位置
    build(p,s1+1,s2,s);    //左子树的结点数为p
    build(len-1-p,s1+p+1,s2+p+1,s+p);    //右子树的结点数为len-1-p
}
int main()
{
char s1[MAXLEN],s2[MAXLEN],ans[MAXLEN];
while(scanf("%s%s",s1,s2)==2)
    {
int len=strlen(s1);
        build(len,s1,s2,ans);
        ans[len]='\0';
        printf("%s\n",ans);
    }
return 0;
}