【题意】
二叉树是每个内部结点最多只有两个子结点且两个子结点有序的树。如下图就是一棵二叉树:
对于一棵二叉树,有三种基本遍历方式:
1.前序遍历:先访问根结点,然后再前序遍历左子树,最后前序遍历右子树;
2.中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树;
3.后序遍历:先后序遍历左子树,然后后序遍历右子树,最后访问根结点。
对于上图,前序遍历的结果是ABDEHCFGI。中序遍历的结果是DBEHAFCIG,后序遍历的结果是DHEBFIGCA。
现在给出二叉树的前序和中序遍历,请输出相应的后序遍历。
【输入格式】
第一行前序遍历的结果
第二行中序遍历的结果
都是大写字母,且结点的标识不重复,最多只有26个结点。
【输出格式】
输出后序遍历的结果
【输入样例】
ABDEHCFGI
DBEHAFCIG
【输出样例】
DHEBFIGCA