Problem1034--[视频]递归4(二叉树的后序遍历)

1034: [视频]递归4(二叉树的后序遍历)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 24  Solved: 13
[Status] [Submit] [Creator:]

Description

【题意】
    二叉树是每个内部结点最多只有两个子结点且两个子结点有序的树。如下图就是一棵二叉树:

    对于一棵二叉树,有三种基本遍历方式:
    1.前序遍历:先访问根结点,然后再前序遍历左子树,最后前序遍历右子树;
    2.中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树;
    3.后序遍历:先后序遍历左子树,然后后序遍历右子树,最后访问根结点。
    对于上图,前序遍历的结果是ABDEHCFGI。中序遍历的结果是DBEHAFCIG,后序遍历的结果是DHEBFIGCA。
    现在给出二叉树的前序和中序遍历,请输出相应的后序遍历。
【输入格式】
    第一行前序遍历的结果
    第二行中序遍历的结果
    都是大写字母,且结点的标识不重复,最多只有26个结点。
【输出格式】
    输出后序遍历的结果
【输入样例】
ABDEHCFGI
DBEHAFCIG
【输出样例】
DHEBFIGCA

Source/Category