题目大意:
给一棵树的中序排列 后序排列,求这棵树的先序排列
https://www.luogu.org/problemnew/show/P1030
后序排列中 子树的最高层是一段排列中的最后一个
中序排列中 树(子树)的排列被其最高层分为左子树和右子树
即一棵树为
1
/ \
2 3
/ \
4 5
则其后序排列为 2 4 5 3 1
中序排列为 2 1 4 3 5
过程如下,()内为已得到的部分先序排列
首先后序找到 54321 排列的最后一个为1,即最高层 (1)
则中序中 21435 被1分为 2 和 435,即左子树为2右子树为435
那么后序中去掉1后的2453,则对应分为 2 和 453 (12)
后序中剩 453 ,即3为最高层(123)
中序中435,分为 4 和 5
后序中对应地分为 4 和 5 (12345)
#include <bits/stdc++.h>
using namespace std;
char in[],po[];
void pre(int L1,int R1,int L2,int R2)
{
if(L1>R1) return;
printf("%c",po[R2]);
int i;
for(i=L1;i<=R1;i++)
if(in[i]==po[R2]) break;
int j=L2+i-L1;
if(i>L1) pre(L1,i-,L2,j-);
if(i<R1) pre(i+,R1,j,R2-);
}
int main()
{
while(~scanf("%s%s",in,po)) {
int len=strlen(in)-;
pre(,len,,len);
cout<<endl;
} return ;
}