求前序遍历

题目描述:

若一棵二叉树，其前序遍历为ABDEGCFHI，中序遍历为DBGEACHFI，后序遍历为DGEBHIFCA。

可以证明，在已知中序和后序遍历的情况下，可以唯一确定二叉树的前序遍历。你的任务就是根据给出的中序和后序遍历，输出前序遍历。 

输入格式:

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

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

树的结点一律用大写字母表示，结点个数不多于26个。

输出格式:

输出树的前序遍历。

样例输入:

DBGEACHFI
DGEBHIFCA

样例输出:

ABDEGCFHI

提示:

完善程序：

def preorder( mid, post ):
    if len(post )==1:
        print( post[0], end="" )
    else:
        print( post [-1], end="" )        
        mfind = mid.index( post[-1] )
        if mfind > 0:  #存在左子树
            preorder( ______________________________ )
        if mfind != len( mid )-1 : #存在右子树
            preorder( ______________________________ )

mid =list(input())
post =list(input())
preorder( mid, post )

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创