CODEVS 1013 求先序排列

题目描述 Description

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

输入描述 Input Description

两个字符串,分别是中序和后序(每行一个)

输出描述 Output Description

一个字符串,先序

样例输入 Sample Input

BADC

BDCA

样例输出 Sample Output

ABCD

数据范围及提示 Data Size & Hint

#include<cstdio>
#include<cstring>
char hou[10],zhon[10];
int find(char *a,char x){
    for(int i = 0;i <= strlen(a)-1;++ i){
        if(a[i]==x) return i;
    }
}
void work(int l1,int r1,int l2,int r2){//1 -> zhon | 2 -> hou
    int mid = find(zhon,hou[r2]);
    printf("%c",zhon[mid]);//root
    if(mid > l1) work(l1,mid-1,l2,l2+mid-l1-1);//left
    if(mid < r1) work(mid+1,r1,r2+mid-r1,r2-1);//right
}
int main(){
    scanf("%s %s",zhon,hou);
    work(0,strlen(zhon)-1,0,strlen(hou)-1);
    return 0;
}

 

此条目发表在CODEVS, NOIP分类目录。将固定链接加入收藏夹。