【题目描述】

树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。 假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。

【输入】

两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。

【输出】

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

【输入样例】

DBEAC
ABCDE

【输出样例】

ABDEC

#include<iostream>
#include<cstring>
using namespace std;
string sta,stb;
int lena,lenb;
void xian(int L,int R){
    if(L>R) return;
    int x;
    for(int i=0;i<=lenb;++i){
        x=sta.find(stb[i]); 
        if(x>=L&&x<=R ){
            cout<<stb[i];
            break; //利用 x 分割
        }
    }
    if(x-1>=L)xian(L, x-1); //在左树中找
    if(x+1<=R)xian(x+1, R); //在右树中找
}
int main(){
    cin>>sta>>stb;
    lena=sta.length()-1;//中序
    lenb=stb.length()-1;//按层
    xian(0,lena);
    return 0;
}//ok