根据中序和后序遍历求根节点

题目描述

给定一棵二叉树的中序遍历序列和后序遍历序列，请输出这棵二叉树的根节点。

在二叉树的后序遍历中，遍历顺序为：

左子树 → 右子树 → 根节点

因此，后序遍历序列的最后一个字符就是整棵二叉树的根节点。

输入格式

输入共两行：

第一行是一个字符串，表示二叉树的中序遍历序列。

第二行是一个字符串，表示二叉树的后序遍历序列。

输出格式

输出一个字符，表示该二叉树的根节点。

输入样例

DBEAC
DEBCA

输出样例

A

样例解释

后序遍历序列为：

DEBCA

最后一个字符是 A，所以这棵二叉树的根节点是 A。

数据范围

设输入字符串长度为 n。

1 ≤ n ≤ 1000

输入的两个字符串长度相同，且均由大写英文字母组成。

保证输入数据对应一棵合法二叉树。