输入第一行给出一个正整数n（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

### 回答1：
题目描述：

给定一棵二叉树的后序遍历和中序遍历，求该二叉树的层序遍历。

输入格式：

第一行给出一个正整数n（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

输出该二叉树的层序遍历序列，数字间以空格分隔，行末不能有多余空格。

输入样例：

9
1 3 2 5 7 6 4 9 8
1 2 3 4 5 6 7 8 9

输出样例：

4 2 8 1 6 9 3 5 7

思路分析：

根据后序遍历和中序遍历可以确定一棵二叉树，然后对该二叉树进行层序遍历即可。

具体实现：

1. 首先根据后序遍历和中序遍历构建二叉树。

2. 然后对该二叉树进行层序遍历，输出结果。

代码实现：

### 回答2：
这道题要求我们根据二叉树的中序遍历和后序遍历序列构造出一棵二叉树，并输出其层序遍历序列。对于这种题目，我们可以使用递归的方法来构造出整棵二叉树。

首先，我们知道后序遍历序列的最后一个元素一定是二叉树的根节点，而中序遍历序列中，根节点的左边是其左子树的节点，右边是其右子树的节点。因此，我们可以在中序遍历序列中找到根节点，将其左边的序列作为左子树的中序遍历序列，将其右边的序列作为右子树的中序遍历序列。此时，在后序遍历序列中，左子树的序列和右子树的序列就分别对应了左子树和右子树的后序遍历序列。接下来，我们可以对左子树和右子树进行递归处理，构造出左右子树。最后，在构造出整棵二叉树后，我们可以使用队列进行层序遍历，输出对应的值即可。

需要注意的是，当中序遍历序列只有一个元素时，我们就已经找到了叶子节点，这时候直接返回一个叶子节点即可。

下面是具体的代码实现：

### 回答3：
题目描述：

此题需要根据二叉树的先序遍历和后序遍历，通过重构还原出二叉树。其中，先序遍历只需从左到右先序输出所有节点，而后序遍历则先从左到右遍历所有节点的左孩子，接着从左到右遍历所有节点的右孩子，然后最后输出整个二叉树的根节点。

分析思路：

此题可采用递归方法进行实现。由于后序遍历遍历的顺序是从左到右，所以最后一个值一定是根节点，而在中序遍历中，根节点分割了左右两棵子树，左边为左子树，右边为右子树。因此可通过递归的方法，先通过后序遍历确定当前二叉树的根节点，再在中序遍历中找到根节点的位置，从而分别确定左子树和右子树。依次递归实现即可。

代码实现：

#此为树节点类，包含左子树、右子树和节点值
class treeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None

#通过后序遍历和中序遍历重建二叉树
def rebuildTree(post, inorder):
if post:
root = treeNode(post[-1])#通过后序遍历确定根节点
index = inorder.index(root.val)#在中序遍历中找到根节点位置，从而分别确定左右子树
root.left = rebuildTree(post[:index], inorder[:index])
root.right = rebuildTree(post[index:-1], inorder[index + 1:])
return root

#输出先序遍历
def preOrder(root):
if not root:
return
print(root.val, end = ' ')
preOrder(root.left)
preOrder(root.right)

#输入测试用例
n = int(input())
postOrder = list(map(int, input().split()))
inOrder = list(map(int, input().split()))

#输出结果
root = rebuildTree(postOrder, inOrder)
preOrder(root)

参考文献：

python数据结构与算法之美