题目描述

农夫约翰对奶牛的传承非常的重视。

他的每头牛都有一个唯一的大写字母编号。

他用一个二叉树记录了牛的传承关系，示例如下：

              C
            /   \
           /     \
          B       G
         / \     /
        A   D   H
           / \
          E   F

现在，给定这个二叉树的中序遍历和前序遍历，请你求出这个二叉树的后序遍历。

中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。
前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。
后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。

输入格式
一个大写字母构成的字符串，表示树的中序遍历。

一个大写字母构成的字符串，表示树的前序遍历。

输出格式
输出一个字符串，表示树的后序遍历。

数据范围
树中结点的数目不超过 26 个。

输入样例：
ABEDFCHG
CBADEFGH
输出样例：
AEFDBHGC

算法分析
由于要求输出后序遍历，我们可以先输出一个树的左子树/右子树，然后再输出根节点，由于树是属于递归定义的一种数据结构，我们也可以递归实现输出，对于任何一棵树，前序遍历的第一个点是当前树的根节点，然后我们可以由中序遍历处理左右子树的节点输出，然后再输出根节点。

#include<bits/stdc++.h>
using namespace std;
void dfs(string a,string b)
{
    if(a.size()==0) return ;
    int t=b.find(a[0]); //左子树节点个数
    dfs(a.substr(1,t),b.substr(0,t));//左子树
    dfs(a.substr(t+1),b.substr(t+1)); //右子树
    cout<<a[0];//当前树的根节点

}
int main()
{
    string a,b;
    cin>>b>>a;
    dfs(a,b);
    return 0;
}