题目描述

给出一棵二叉树的中序遍历和后序遍历，求它的先序遍历。

约定树中每个结点用不同的大写字母表示。

输入格式

两行字符串。

第一行表示中序遍历，第二行表示后序遍历。

输出格式

一行一个字符串，表示这棵二叉树的先序遍历。

样例输入 #1

BADC
BDCA

样例输出 #1

ABCD

数据范围与提示

字符串长度不超过 8，且同一棵树中的结点互不相同。

后序遍历的最后一个字符是根结点；在中序遍历中，根结点左边是左子树，右边是右子树。

来源

洛谷 P1030 [NOIP2001 普及组] 求先序排列。