比赛 noip2016普及练习1 评测结果 AAAAA
题目名称 求先序遍历 最终得分 100
用户昵称 Lethur 运行时间 0.015 s
代码语言 C++ 内存使用 15.59 MiB
提交时间 2016-11-03 20:50:33
显示代码纯文本
#include <iostream>
#include <string.h>
#include <sstream>
#include <stdio.h> 
#include <algorithm>
using namespace std;

const int maxn=1001000;
int in_order[maxn],post_order[maxn],lch[maxn],rch[maxn];
int n;

void read_list(int *a)
{
    char line[10];
    scanf("%s",line);
    n=0;
    int x=-1;
    while(line[++x]<='Z'&&line[x]>='A')a[n++]=line[x]-'A'+1;
    return;
}

int build(int L1,int R1,int L2,int R2)
{
    if(L1>R1)return 0;
    int root=post_order[R2];
    int p=L1;
    while(in_order[p]!=root)p++;
    int cnt=p-L1;
    lch[root]=build(L1,p-1,L2,L2+cnt-1);
    rch[root]=build(p+1,R1,L2+cnt,R2-1);
    return root;
}
void print(int node)
{
    printf("%c",node-1+'A');
    if(lch[node])print(lch[node]);
    if(rch[node])print(rch[node]);
}
int main()
{
	freopen("nlr.in","r",stdin);
	freopen("nlr.out","w",stdout);
    read_list(in_order); 
    read_list(post_order);
    build(0,n-1,0,n-1); 
    print(post_order[n-1]);
}