【题目描述】

输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。

【输入】

共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。

【输出】

一行，表示树的后序遍历序列。

【输入样例】

abdec
dbeac

【输出样例】

debca

#include<iostream>
#include<cstring>
using namespace std;
string sta,stb;
void hou(int la,int ra,int lb,int rb){
    int lx=stb.find(sta[la]);
    if(lx>lb)hou(la+1, la+(lx-lb), lb, lx-1);
    //取左树  sta切首(量长)    stb 取根左
    if(lx<rb)hou(la+(lx-lb)+1, ra, lx+1, rb);
    //取右树  sta切过左树     stb 取根右
    cout<<sta[la];//根最后输出
}
int main(){
    cin>>sta>>stb;
    int ra=sta.length()-1;
    int rb=stb.length()-1;
    hou(0,ra,0,rb);
    return 0;
}//ok
/*         (la)    (ra)
            |       |
先根 sta:   a b d e c

          (lb)   (lx) (rb)
            |     |  |
中根 stb:   d b e a c

*/