1468: 已知先序遍历和中序遍历,输出后序遍历
内存限制:65535 MB
时间限制:1000 S
评测方式:文本比较
命题人:外部导入
提交:250
解决:94
题目描述
理解先序遍历和中序遍历:
先序遍历(根左右):先访问根节点,然后访问左子树,最后访问右子树。
中序遍历(左根右):先访问左子树,然后访问根节点,最后访问右子树。
递归求解后序遍历:
从先序遍历中确定根节点。
在中序遍历中找到根节点的位置,以此划分左子树和右子树。
递归地对左子树和右子树进行同样的操作,直到没有子树为止。
最后将左右子树的节点和根节点按后序遍历的顺序输出。
具体步骤:
确定根节点:先序遍历的第一个元素是根节点。
划分左右子树:在中序遍历中找到根节点的位置,左边的部分是左子树,右边的部分是右子树。
递归处理:对左子树和右子树重复上述过程,直到没有子树为止。
输出后序遍历:按照后序遍历的顺序(左右根)输出所有节点的值。
示例:
先序遍历:ABDECFH
中序遍历:BDCEAHF
后序遍历:CEDBHFA
先序遍历(根左右):先访问根节点,然后访问左子树,最后访问右子树。
中序遍历(左根右):先访问左子树,然后访问根节点,最后访问右子树。
递归求解后序遍历:
从先序遍历中确定根节点。
在中序遍历中找到根节点的位置,以此划分左子树和右子树。
递归地对左子树和右子树进行同样的操作,直到没有子树为止。
最后将左右子树的节点和根节点按后序遍历的顺序输出。
具体步骤:
确定根节点:先序遍历的第一个元素是根节点。
划分左右子树:在中序遍历中找到根节点的位置,左边的部分是左子树,右边的部分是右子树。
递归处理:对左子树和右子树重复上述过程,直到没有子树为止。
输出后序遍历:按照后序遍历的顺序(左右根)输出所有节点的值。
示例:
先序遍历:ABDECFH
中序遍历:BDCEAHF
后序遍历:CEDBHFA
输入
两行字符串,每行字符串长度不超过26个。
输出
一行字符串
样例输入 复制
ABDECFH
BDCEAHF
样例输出 复制
CEDBHFA