比赛 |
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]);
}