求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入输出格式

输入格式：

2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式：

1行，表示一棵二叉树的先序。

输入输出样例

输入样例#1：

BADC

BDCA

输出样例#1：

ABCD

noip2001普及组第三题

------------------------------------------------------------------------------------------------------------------------------------------------------------------

普及一下遍历：https://www.cnblogs.com/lhc-yyl-lyx-lyh/p/8439997.html

讲解：

首先后序遍历有一个性质，后序遍历的最后一个就是根。又因为题目约定树结点用不同的大写字母表示，所以对于两个遍历，找到后序遍历的最后一个（就是根），在中序遍历中找到这个字母把中序遍历分成两段。那么后续遍历怎么办？中序遍历前半段的个数，就是后序遍历的前半段。这个过程用递归实现，先序遍历在递归中自然就完成了。示例：

中序ACGDBHZKX，后序CDGAHXKZB，

首先可找到主根B；那么我们找到中序遍历中的B，由这种遍历的性质，

可将中序遍历分为ACGD和HZKX两棵子树，

那么对应可找到后序遍历CDGA和HXKZ

从而问题就变成求1.中序遍历ACGD，后序遍历CDGA的树

中序遍历HZKX，后序遍历HXKZ的树

代码实现：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int book[28],len,cnt;
char ans[10],a[10],b[10];
void ff(int l1,int r1,int l2,int r2)
{
    if(l2==r2) return;
    ans[cnt++]=b[r2-1];
    if(l2==r2-1) return;
    int k=book[b[r2-1]-'A'];
    ff(l1,k,l2,(k-l1)+l2);
    ff(k+1,r1,r2-1-(r1-k-1),r2-1);//琢磨琢磨吧 
    return;
}
int main()
{
    int i,j;
    scanf("%s%s",&a,&b);
    len=strlen(a);
    for(i=0;i<len;i++) book[a[i]-'A']=i;//方便寻找 
    ff(0,len,0,len);//左闭右开的区间 
    for(i=0;i<cnt;i++) cout<<ans[i];
    return 0;
}

View Code