给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。\n\n输入格式：\n输入第一行给出一个正整数n（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第

### 回答1：
三行给出其中序遍历序列。数字间以空格分隔。

输出格式：
在一行中输出该树的层序遍历序列。数字间以1个空格分隔，行末不得有多余空格。

输入样例：
9
1 3 2 5 7 6 4 9 8
1 2 3 4 5 6 7 8 9
输出样例：
4 6 8 1 3 5 7 2 9

### 回答2：
三行给出中序遍历序列。\n\n输出格式：\n在一行中输出该树的层序遍历序列。数字间以1个空格分隔，行末不得有多余空格。\n\n输入样例：\n7\n2 3 1 5 7 6 4\n1 2 3 4 5 6 7\n输出样例：\n4 1 6 3 5 7 2\n\n题目解析：\n给定一棵二叉树的后序遍历和中序遍历，要求输出其层序遍历的序列。针对这个问题，需要使用到树的层序遍历的方法，而代码中最常用的层序遍历方法就是基于队列的 BFS。\n\n基本思路：\n1.根据后序遍历和中序遍历构造出二叉树；\n2.对构造得到的二叉树进行层序遍历；\n3.输出层序遍历得到的序列。\n\n构造二叉树的过程\n1.后序遍历序列的最后一个元素就是根节点；\n2.在中序遍历中找到根节点的位置，则根节点左边就是左子树的中序遍历，右边就是右子树的中序遍历；\n3.通过在后序遍历序列中找到左子树和右子树的位置，可以确定左右子树的后序遍历序列，对左右子树分别进行递归构造。\n在递归实现的过程中，每个子问题的求解都会由底向上返回，这样就可以通过 BFS 层序遍历输出最终的层序遍历序列。代码实现大致分为两部分：\n1.构造二叉树，返回根节点；\n2.BFS 输出层序遍历的序列。

### 回答3：
题目要求输出一棵二叉树的层序遍历序列，给定了该树的后序遍历序列和中序遍历序列。层序遍历是按层遍历，从上到下，从左到右，也就是 BFS 算法的应用。而后序遍历是从底部开始的，根节点在最后访问，中序遍历则是根节点在中间访问，因此我们需要利用这两个序列来重建一棵二叉树，然后对该二叉树进行层序遍历。

先解决如何建树的问题。后序遍历的最后一个元素就是根节点，我们根据根节点可以将中序遍历序列分为左右两部分，再根据这两部分的长度，可以确定左右子树中的元素个数，进而递归地建立该树。

建树完成后，我们就可以对该二叉树进行 BFS 遍历，输出各节点的值即可。

具体实现代码如下：

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

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

from collections import deque
def levelOrderTraversal(root):
    if not root:
        return []
    res = []
    q = deque()
    q.append(root)
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

n = int(input())
postorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))
root = buildTree(inorder, postorder)
res = levelOrderTraversal(root)
for i in range(len(res)):
    print('Level {}:'.format(i+1), end=' ')
    print(' '.join(map(str, res[i])))

时间复杂度：

建树的时间复杂度是 $O(n\log n)$，遍历二叉树的时间复杂度是 $O(n)$，因此总时间复杂度是 $O(n\log n)$。