第一行给出正整数n(≤30)，是树中结点的个数。随后两行，每行给出n个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

题目描述：

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

输入格式：

第一行给出正整数n(≤30)，是树中结点的个数。随后两行，每行给出n个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式：

输出该二叉树的层序遍历结果，数字间以空格分隔，最后一个数字后面不能有空格。

样例输入：

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

样例输出：

4 6 8 1 5 9 2 3 7

算法1

(递归) $O(n^2)$

1.后序遍历的最后一个节点为根节点，找到根节点在中序遍历中的位置，左边为左子树，右边为右子树。

2.递归构建左子树和右子树。

3.输出根节点。

时间复杂度

最坏情况下，每次递归都需要遍历整个中序遍历数组，时间复杂度为 $O(n^2)$。

C++ 代码

算法2

(递归) $O(n)$

1.后序遍历的最后一个节点为根节点，找到根节点在中序遍历中的位置，左边为左子树，右边为右子树。

2.递归构建左子树和右子树。

3.输出根节点。

时间复杂度

每个节点只遍历一次，时间复杂度为 $O(n)$。

C++ 代码

相关问题

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。\n\n输入格式:\n第一行给出正整数n(≤30)，是树中结点的个数。随后两行，每行给出n个整数，分别对应后序遍历和中序遍历结果

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

给定一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式：

第一行给出正整数n(≤30)，是树中结点的个数。随后两行，每行给出n个整数，分别对应后序遍历和中序遍历结果。

输出格式：

输出该树的先序遍历结果，数字间有一个空格，行末不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 3 2 6 5 7

解题思路：

根据后序遍历和中序遍历的结果，可以确定根节点和左右子树的中序遍历结果。然后根据左右子树的中序遍历结果，可以得到左右子树的后序遍历结果。递归处理左右子树，最后得到整棵树的先序遍历结果。

代码实现：

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

本题给定一棵二叉树的后序遍历和中序遍历结果，要求输出该树的先序遍历结果。

输入格式：

第一行给出正整数n(≤30)，是树中结点的个数。

随后两行，每行给出n个整数，分别对应后序遍历和中序遍历结果。

解题思路：

对于二叉树的遍历问题，通常采用递归的方法处理。

我们可以根据后序遍历的特性，确定该数组最后一个元素就是根节点，然后在中序遍历数组中查找根节点，从而可以确定左子树和右子树的节点数目。

然后，我们再递归地处理左子树和右子树，并依次输出先序遍历结果。

时间复杂度：O(n^2)

代码实现：

### 回答3：
本题需要我们根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。题目包含三个关键词：后序遍历、中序遍历和先序遍历，这三种遍历方式都是二叉树遍历的方式。其中，后序遍历指的是先遍历左子树，再遍历右子树，最后遍历根节点，中序遍历指的是先遍历左子树，再遍历根节点，最后遍历右子树，而先序遍历则是指先遍历根节点，再遍历左子树，最后遍历右子树。通过后序遍历和中序遍历结果，我们可以还原出完整的二叉树，然后再进行先序遍历输出。

由于是后序遍历，最后一个节点一定是根节点，由此可以将中序遍历结果分为根节点的左子树和右子树。对于后序遍历来说，根节点的前一个节点是右子树的根节点，而根节点之前的所有节点都是左子树的节点。因此，我们可以不断地递归去解决左右子树的问题。

具体做法如下：

1.读入后序遍历和中序遍历的结果，存储到数组中。创建一个函数，传入后序遍历和中序遍历数组、左右子树的起止下标，返回当前子树的根节点。

2.在函数中，先找到当前子树的根节点，即后序遍历的最后一个节点，然后在中序遍历的结果中搜索该节点，找到该节点的位置，即为当前子树的根节点位置。

3.根据该节点位置，可以得到该节点左右两边分别属于左子树和右子树，然后递归调用该函数，分别求出左右子树的根节点。

4.输出当前子树的根节点，并将其返回。

5.在主函数中调用该函数，输出整棵树的先序遍历结果。

代码实现如下（Python）：

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。 输出格式: 在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

好的，根据你给出的问题，我会回答你的。但是，我是一个语言模型，并没有记忆功能，所以我无法知道你之前是否告诉过我这段话。不过没关系，我会根据你的问题进行回答。

根据你的描述，这是一道关于二叉树遍历的题目。根据后序遍历和中序遍历的结果，我们可以通过递归的方式构造出一棵二叉树，并输出该树的先序遍历结果。

具体来说，我们可以通过后序遍历的最后一个节点得到该树的根节点，在中序遍历中找到该节点，从而确定左子树和右子树的节点数量，并递归构造出左子树和右子树。最后，按照根节点、左子树、右子树的顺序输出即可得到先序遍历结果。

以下是 Python 代码实现：