1468: 已知先序遍历和中序遍历,输出后序遍历

内存限制:65535 MB 时间限制:1000 S
评测方式:文本比较 命题人:外部导入
提交:250 解决:94

题目描述

理解先序遍历和中序遍历:

先序遍历(根左右):先访问根节点,然后访问左子树,最后访问右子树。
中序遍历(左根右):先访问左子树,然后访问根节点,最后访问右子树。
递归求解后序遍历:

从先序遍历中确定根节点。
在中序遍历中找到根节点的位置,以此划分左子树和右子树。
递归地对左子树和右子树进行同样的操作,直到没有子树为止。
最后将左右子树的节点和根节点按后序遍历的顺序输出。
具体步骤:

确定根节点:先序遍历的第一个元素是根节点。
划分左右子树:在中序遍历中找到根节点的位置,左边的部分是左子树,右边的部分是右子树。
递归处理:对左子树和右子树重复上述过程,直到没有子树为止。
输出后序遍历:按照后序遍历的顺序(左右根)输出所有节点的值。
示例:

先序遍历:ABDECFH
中序遍历:BDCEAHF
后序遍历:CEDBHFA

输入

两行字符串,每行字符串长度不超过26个。

输出

一行字符串

样例输入 复制

ABDECFH
BDCEAHF

样例输出 复制

CEDBHFA

提示