1772: [树]二叉树先中求后

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:5 Solved:5

Description

一棵二叉树,其先序遍历为ABDRGCFHI,中序遍历为DBGEACHFI,后序遍历为DGEBHIFCA。

    可以证明,在已知先序和中序遍历的情况下,可以唯一确定二叉树的后序遍历。根据给出的先序和中序遍历,输出后序遍历。

Input

第一行一个字符串,表示树的先序遍历。

第二行一个字符串,表示树的中序遍历。

树的结点一律用大写字母表示。

Output

输出树的后序遍历,一行字符。

Sample Input Copy

ABDEGCFHI
DBGEACHFI

Sample Output Copy

DGEBHIFCA

Source/Category