给出一棵二叉树的中序与后序排列。求出它的先序排列

### 回答1：
由于中序和后序排列已知，可以通过递归的方式求出先序排列。

先找到后序排列的最后一个元素，即为根节点。然后在中序排列中找到根节点的位置，将中序排列分成左子树和右子树两部分。接着递归处理左子树和右子树，直到叶子节点。

具体步骤如下：

1. 找到后序排列的最后一个元素，即为根节点。
2. 在中序排列中找到根节点的位置，将中序排列分成左子树和右子树两部分。
3. 根据左子树和右子树的元素个数，将后序排列分成左子树和右子树两部分。
4. 递归处理左子树和右子树，直到叶子节点。
5. 将根节点加入先序排列中。

最终得到的先序排列即为该二叉树的先序排列。

例如，给出中序排列为[4, 2, 5, 1, 6, 3, 7]，后序排列为[4, 5, 2, 6, 7, 3, 1]，则可以得到先序排列为[1, 2, 4, 5, 3, 6, 7]。

### 回答2：
求一棵二叉树的先序遍历需要知道它的根节点位置，而中序遍历和后序遍历无法直接确定根节点的位置。因此，我们需要先通过中序遍历和后序遍历构建出这棵二叉树，然后再进行先序遍历。

具体步骤如下：

1. 后序遍历的最后一个节点肯定是二叉树的根节点，假设它是节点p。
2. 在中序遍历中找到节点p的位置，它将中序遍历序列分成了左子树和右子树两部分。
3. 根据左右子树的长度，在后序遍历中将序列分成两部分，分别对应左子树和右子树的后序遍历。
4. 对左子树和右子树分别递归执行上述步骤，构建出左子树和右子树。
5. 将根节点p加入先序遍历序列中，然后依次加入左子树和右子树的先序遍历序列，即为最终的先序遍历序列。

举个例子，假设中序遍历为[4, 2, 5, 1, 6, 3, 7]，后序遍历为[4, 5, 2, 6, 7, 3, 1]。根据上述步骤，可以构建出如下的二叉树：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

由于后序遍历的最后一个节点是1，因此1是根节点。在中序遍历中，4和5在1的左侧，2在其左侧，6和7在其右侧，3在其右侧，因此左子树的中序遍历为[4, 2, 5]，右子树的中序遍历为[6, 3, 7]。同理，左子树的后序遍历为[4, 5, 2]，右子树的后序遍历为[6, 7, 3]。按照上述步骤分别构建出左子树和右子树即可。最终的先序遍历序列为[1, 2, 4, 5, 3, 6, 7]。

总结起来，通过中序遍历和后序遍历构建出二叉树的步骤如下：

1. 后序遍历的最后一个节点是二叉树的根节点。
2. 在中序遍历中找到根节点的位置，将中序遍历序列分成左子树和右子树两部分。
3. 根据左右子树的长度，将后序遍历序列分成左子树和右子树的后序遍历序列。
4. 分别对左子树和右子树递归执行上述步骤，构建出左子树和右子树。
5. 根节点加入先序遍历序列，然后依次加入左子树和右子树的先序遍历序列，得到最终的先序遍历序列。

### 回答3：
我们可以使用递归的方式求解这个问题。先看一下先序、中序和后序排列的定义：

- 先序遍历：先访问根节点，再遍历左子树和右子树。
- 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。
- 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。

根据后序排列，我们可以得到该二叉树的根节点，然后在中序排列中找到根节点所在的位置，这将中序排列分成了左子树和右子树两部分。再根据左子树和右子树的节点数量，将后序排列也分成了左子树和右子树两部分。这时我们就可以递归地对左子树和右子树进行求解，直到节点数量为1或0，即到达了叶子节点或者空节点。

对于每个子树，我们都可以通过递归得到它的先序排列。具体的方法是先输出根节点，再递归输出左子树和右子树的先序排列。

下面是一个Python实现：

def construct_tree(inorder, postorder):
    if len(postorder) == 0:
        return None
    root = TreeNode(postorder[-1])
    index = inorder.index(postorder[-1])
    left_inorder = inorder[:index]
    right_inorder = inorder[index+1:]
    left_size = len(left_inorder)
    right_size = len(right_inorder)
    left_postorder = postorder[:left_size]
    right_postorder = postorder[left_size:-1]
    root.left = construct_tree(left_inorder, left_postorder)
    root.right = construct_tree(right_inorder, right_postorder)
    return root

def preorder_traversal(root):
    if root is None:
        return []
    result = [root.val]
    result += preorder_traversal(root.left)
    result += preorder_traversal(root.right)
    return result

inorder = [4,2,5,1,6,3,7]
postorder = [4,5,2,6,7,3,1]
root = construct_tree(inorder, postorder)
print(preorder_traversal(root))

输出结果为：[1, 2, 4, 5, 3, 6, 7]，即该二叉树的先序排列。