PTA 7-1 根据后序和中序遍历输出先序遍历python

思路：由于后序遍历的最后一个元素即为根节点，因此可以先找到根节点在中序遍历中的位置，然后将中序遍历分成左子树和右子树两部分。再根据左右子树的长度，在后序遍历中将其分为左子树和右子树两部分。然后对左右子树分别进行递归，直到叶子节点。

Python代码如下：

def post_in_to_pre(inorder, postorder):
    if not inorder or not postorder:
        return ''
    root = postorder[-1]
    index = inorder.index(root)
    left_inorder = inorder[:index]
    right_inorder = inorder[index+1:]
    left_postorder = postorder[:index]
    right_postorder = postorder[index:-1]
    left_preorder = post_in_to_pre(left_inorder, left_postorder)
    right_preorder = post_in_to_pre(right_inorder, right_postorder)
    return root + left_preorder + right_preorder

# 测试
inorder = 'DBEAFC'
postorder = 'DEBFCA'
print(post_in_to_pre(inorder, postorder))  # 输出ABDECF

时间复杂度：$O(nlogn)$