描述

二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入描述：

两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C…最多26个结点。 输出描述： 输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。

示例1
输入：

ABC
BAC
FDXEAG
XDEFAG

输出：

BCA
XEDGAF

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
struct node {char data;node * left, * right; 
}; 
node * create_tree(string pre, string in)
{if(pre.length() == 0)return NULL;node * root = new node;root->data = pre[0];root->left = root->right = NULL;int rootid = in.find(pre[0]);root->left = create_tree(pre.substr(1, rootid), in.substr(0, rootid));root->right = create_tree(pre.substr(rootid+1), in.substr(rootid+1));return root;	
}
void post_order(node * root)
{if(root == NULL)return;post_order(root->left);post_order(root->right);printf("%c", root->data);
}
int main()
{string pre, in;while(cin >> pre >> in){node * root = NULL;root = create_tree(pre, in);post_order(root);printf("\n");}
}