一棵二叉树,其先序遍历为ABDRGCFHI,中序遍历为DBGEACHFI,后序遍历为DGEBHIFCA。
可以证明,在已知先序和中序遍历的情况下,可以唯一确定二叉树的后序遍历。根据给出的先序和中序遍历,输出后序遍历。
第一行一个字符串,表示树的先序遍历。
第二行一个字符串,表示树的中序遍历。
树的结点一律用大写字母表示。
输出树的后序遍历,一行字符。
ABDEGCFHI DBGEACHFI
DGEBHIFCA