洛谷 P1030 求先序排列

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

BADC
BDCA

输出样例#1：

ABCD

搜索 
屠龙宝刀点击就送

#include<cstdio>
#include<cstring>
int t,q;
char last[9],mid[9],c[100];
char gen(int l,int r)
{
    int i,j;
    for(i=t;i>=0;i--)
    {
        for(j=l;j<=r;j++)
        {
            if(mid[j]==last[i])
            return mid[j];
        }
    }
}
void find(int l,int r)
{
    int i;
    char k;
    k=gen(l,r);
    c[q++]=k;
    for(i=l;i<=r;i++)
    {
        if(mid[i]==k)
        {
            break;
        }
    }
    if(l<=i-1)
    find(l,i-1);
    if(i+1<=r)
    find(i+1,r);
}
int main()
{
    int i,j;
    scanf("%s",mid);
    getchar();
    scanf("%s",last);
    t=strlen(mid)-1;
    find(0,t);
    printf("%s",c);
    return 0;
}