7-1 根据后序和中序遍历输出先序遍历 (25 分)

### 回答1：
根据后序遍历和中序遍历序列，可以构造出二叉树。首先需要确定根节点，后序遍历的最后一个元素就是根节点，然后根据中序遍历的结果，可以将左子树和右子树的节点划分出来。然后对左子树和右子树递归进行构造。

举个例子，假设后序遍历序列为[9, 15, 7, 20, 3]，中序遍历序列为[9, 3, 15, 20, 7]，那么我们可以发现3是根节点，然后将中序遍历的结果分为左子树[9]和右子树[15, 20, 7]。接着，我们可以根据左子树和右子树的后序遍历序列[9]和[15, 7, 20]，递归构造出左子树和右子树。

最终构造出的二叉树如下所示：

      3
     / \
    9   20
       /  \
      15   7

在输出先序遍历序列时，遵循“根-左-右”的顺序。因此输出序列为[3, 9, 20, 15, 7]。

### 回答2：
根据二叉树的遍历方式，中序遍历的顺序为：左子树、根节点、右子树；后序遍历的顺序为：左子树、右子树、根节点；先序遍历的顺序为：根节点、左子树、右子树。

根据后序和中序遍历输出先序遍历，可以先从后序遍历中确定根节点，再从中序遍历中确定左右子树的节点个数，最后递归处理左右子树，输出先序遍历。

具体实现步骤如下：

1. 根据后序遍历的最后一个节点确定根节点。
2. 在中序遍历中找到根节点的位置，确定左子树和右子树的节点个数。
3. 递归地处理左子树，输出左子树的先序遍历。
4. 递归地处理右子树，输出右子树的先序遍历。
5. 最后输出根节点的值。

具体实现可以参考下面的代码：

def build_tree(in_order, post_order):
    if not post_order:
        return None
    root_val = post_order[-1]
    root = TreeNode(root_val)
    idx = in_order.index(root_val)
    left_in_order = in_order[:idx]
    right_in_order = in_order[idx+1:]
    left_post_order = post_order[:idx]
    right_post_order = post_order[idx:-1]
    root.left = build_tree(left_in_order, left_post_order)
    root.right = build_tree(right_in_order, right_post_order)
    return root

def preorder_traversal(root):
    if root:
        print(root.val, end=' ')
        preorder_traversal(root.left)
        preorder_traversal(root.right)

in_order = [4, 2, 5, 1, 6, 3, 7]
post_order = [4, 5, 2, 6, 7, 3, 1]
root = build_tree(in_order, post_order)
preorder_traversal(root)  # 输出 1 2 4 5 3 6 7

以上代码先定义了两个函数，分别用于构建二叉树和输出先序遍历。构建二叉树的过程跟“105. 从前序与中序遍历序列构造二叉树”类似，只是变成了根据后序和中序遍历构建二叉树。输出先序遍历则是按照根节点、左子树、右子树的顺序输出节点值。

最后调用一下主函数即可得到输出结果。

### 回答3：
对于一棵二叉树，可以通过先序遍历、中序遍历、后序遍历之一来确定其结构。现在给定一棵二叉树的后序遍历和中序遍历，请输出其先序遍历。

首先，我们需要了解什么是先序遍历、中序遍历和后序遍历。

先序遍历：按照“根-左-右”的顺序遍历整棵二叉树。

中序遍历：按照“左-根-右”的顺序遍历整棵二叉树。

后序遍历：按照“左-右-根”的顺序遍历整棵二叉树。

对于本题，我们需要根据给定的后序遍历和中序遍历，来确定该二叉树的结构。

首先，我们可以通过后序遍历的最后一个元素来确定该二叉树的根节点。

其次，我们可以利用中序遍历来确定该二叉树的左子树和右子树。具体来说，可以将中序遍历分为两个部分，分别是左子树和右子树。此时，我们可以根据左子树和右子树的元素数量，来确定左子树和右子树的范围。

最后，我们可以根据左子树和右子树的范围，来递归求解子树。具体来说，我们可以先递归求解右子树，再递归求解左子树。

举个例子，假设给定的后序遍历和中序遍历如下所示：

后序遍历：2 4 3 8 9 6 7 5 1

中序遍历：2 3 4 9 8 5 6 7 1

根据后序遍历，我们可以确定该二叉树的根节点为1。

根据中序遍历，我们可以将其分为左子树和右子树。

左子树：2 3 4

右子树：9 8 5 6 7

此时，我们可以发现，左子树的元素数量为3，右子树的元素数量为5。因此，我们可以确定左子树的范围为后序遍历的倒数第6个元素到倒数第4个元素，右子树的范围为后序遍历的倒数第4个元素到倒数第1个元素。

接下来，我们可以先递归求解右子树，再递归求解左子树。

递归求解右子树时，根据后序遍历的倒数第1个元素可以确定其根节点为5。接着，根据中序遍历，可以将其分为左子树和右子树。

左子树：无

右子树：9 8

此时，我们可以发现，左子树的元素数量为0，右子树的元素数量为2。因此，我们可以确定左子树的范围为空，右子树的范围为后序遍历的倒数第3个元素到倒数第2个元素。

根据递归的方式，我们可以依次求解出右子树的先序遍历为：5 8 9。

接着，我们可以递归求解左子树。此时，根据后序遍历的倒数第7个元素可以确定其根节点为2。接着，根据中序遍历，可以将其分为左子树和右子树。

左子树：无

右子树：3 4

此时，我们可以发现，左子树的元素数量为0，右子树的元素数量为2。因此，我们可以确定左子树的范围为空，右子树的范围为后序遍历的倒数第6个元素到倒数第5个元素。

根据递归的方式，我们可以依次求解出左子树的先序遍历为：2 4 3。

最终，我们可以将右子树的先序遍历和左子树的先序遍历拼接起来，即可得到该二叉树的先序遍历为：1 5 8 9 2 4 3。

总结一下，我们可以通过以下三个步骤来求解二叉树的先序遍历：

1. 根据后序遍历的最后一个元素确定二叉树的根节点。

2. 根据中序遍历将其分为左子树和右子树，确定左子树和右子树的范围。

3. 递归求解左子树和右子树的先序遍历，然后将其拼接起来。