我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根序列，或者给定中根序列和前根序列，可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。 用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树 中根序列是9 5 32 67 后根序列9 32 67 5 前根序列5 9 67 32 输入 两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。 输出 一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。 样例输入 9 5 32 67 9 32 67 5 样例输出 5 9 67 32

以下是 Python 代码实现：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None
    
    root = TreeNode(postorder[-1])
    idx = inorder.index(postorder[-1])
    
    root.left = buildTree(inorder[:idx], postorder[:idx])
    root.right = buildTree(inorder[idx+1:], postorder[idx:-1])
    
    return root

def preorderTraversal(root):
    if not root:
        return []
    
    res = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return res

if __name__ == '__main__':
    inorder = list(map(int, input().split()))
    postorder = list(map(int, input().split()))
    
    root = buildTree(inorder, postorder)
    res = preorderTraversal(root)
    
    print(' '.join(str(x) for x in res))

时间复杂度为 $O(n)$，其中 $n$ 为二叉树的节点数。