02255: 重建二叉树

http://cs101.openjudge.cn/practice/02255/

输入

输入可能有多组，以EOF结束。每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。

输出

对于每组输入，用一行来输出它后序遍历结果。

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB

提示

以英文题面为准

通过递归地划分左右子树并重建二叉树，然后再按照左子树、右子树、根节点的顺序进行后序遍历。

python

def build_tree(preorder, inorder):
    if not preorder:
        return ''
    
    root = preorder[0]
    root_index = inorder.index(root)
    
    left_preorder = preorder[1:1 + root_index]
    right_preorder = preorder[1 + root_index:]
    
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index + 1:]
    
    left_tree = build_tree(left_preorder, left_inorder)
    right_tree = build_tree(right_preorder, right_inorder)
    
    return left_tree + right_tree + root

while True:
    try:
        preorder, inorder = input().split()
        postorder = build_tree(preorder, inorder)
        print(postorder)
    except EOFError:
        break

02255: 重建二叉树 ​

02255: 重建二叉树