设计算法输入中序后序序列，输出先序序列

我们可以通过递归的方式来解决这个问题。首先，根据中序序列和后序序列的定义，后序序列的最后一个元素一定是树的根节点。然后，我们可以在中序序列中找到根节点的位置，根节点左边的所有元素一定是左子树中的节点，右边的所有元素一定是右子树中的节点。而在后序序列中，除了最后一个元素是根节点，其余元素分别属于左子树和右子树。

接下来，我们可以递归地构建左子树和右子树，直到叶节点为止。具体实现如下：

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

def postorder_to_preorder(inorder, postorder):
    root = build_tree(inorder, postorder)
    res = []
    def preorder(node):
        if not node:
            return
        res.append(node.val)
        preorder(node.left)
        preorder(node.right)
    preorder(root)
    return res

其中，`build_tree`函数用来构建树，`postorder_to_preorder`函数用来输出先序序列。时间复杂度为$O(n\log n)$，空间复杂度为$O(n)$。