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

这道题需要我们通过后序遍历和中序遍历重建二叉树，再对重建后的二叉树进行层序遍历。

我们先通过后序遍历和中序遍历重建二叉树。后序遍历的最后一个结点就是二叉树的根结点，然后在中序遍历序列中找到根结点的位置，就可以把中序遍历序列分成左子树和右子树两部分。接着递归处理左子树和右子树，就可以重建整个二叉树。

重建好二叉树后，我们可以通过队列实现层序遍历。从根结点开始，把左右子树加入队列中，然后依次取出队首元素，并把它的左右子树加入队列中，直到队列为空。

代码实现如下：

相关问题

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数

### 回答1：
这道题需要用到二叉树的后序遍历和中序遍历，然后再通过层序遍历输出序列。具体步骤如下：

1. 根据后序遍历找到根节点，然后在中序遍历中找到根节点的位置，将中序遍历分成左子树和右子树两部分。

2. 对左子树和右子树分别进行递归，直到只剩下一个节点或者为空。

3. 对每个节点进行层序遍历，输出序列。

代码实现如下：

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

unordered_map<int, int> inorder_map;

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int in_start, int in_end, int post_start, int post_end) {
    if (in_start > in_end || post_start > post_end) {
        return NULL;
    }
    int root_val = postorder[post_end];
    TreeNode* root = new TreeNode(root_val);
    int root_index = inorder_map[root_val];
    int left_size = root_index - in_start;
    root->left = buildTree(inorder, postorder, in_start, root_index - 1, post_start, post_start + left_size - 1);
    root->right = buildTree(inorder, postorder, root_index + 1, in_end, post_start + left_size, post_end - 1);
    return root;
}

vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    if (!root) {
        return res;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = ; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            res.push_back(node->val);
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }
    return res;
}

vector<int> levelOrderTraversal(vector<int>& inorder, vector<int>& postorder) {
    int n = inorder.size();
    for (int i = ; i < n; i++) {
        inorder_map[inorder[i]] = i;
    }
    TreeNode* root = buildTree(inorder, postorder, , n - 1, , n - 1);
    return levelOrder(root);
}

int main() {
    vector<int> inorder = {9, 3, 15, 20, 7};
    vector<int> postorder = {9, 15, 7, 20, 3};
    vector<int> res = levelOrderTraversal(inorder, postorder);
    for (int i = ; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return ;
}

### 回答2：
这是一道树的遍历的问题，需要先了解二叉树的后序遍历、中序遍历和层序遍历的规则。

后序遍历的顺序是先遍历左子树，再遍历右子树，最后遍历根节点。
中序遍历的顺序是先遍历左子树，再遍历根节点，最后遍历右子树。
层序遍历的顺序是按照每一层从左到右依次遍历树节点。

所以，我们可以根据题意，首先通过后序遍历和中序遍历获取到该二叉树的结构。接下来，我们可以借助队列来实现二叉树的层序遍历。

具体思路如下：
1. 创建一个队列，在队列中先将根节点入队。
2. 当队列不为空时，执行以下步骤：
a. 弹出队列中的最前面的节点，并将其输出。
b. 若该节点有左节点，则将其左节点入队。
c. 若该节点有右节点，则将其右节点入队。
3. 直到队列为空，输出所有节点即可。

综上，我们可以使用Python语言来实现以下代码：

from collections import deque

def levelOrder(inorder, postorder):
    if len(inorder) == 0:
        return []
    rootVal = postorder[-1]
    i = inorder.index(rootVal)
    root = TreeNode(rootVal)
    root.left = levelOrder(inorder[:i], postorder[:i])
    root.right = levelOrder(inorder[i+1:], postorder[i:-1])
    
    queue, res = deque(), []
    queue.append(root)
    while queue:
        level = []
        for i in range(len(queue)):
            node = queue.popleft()
            if node:
                level.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
        if level:
            res.append(level)
    return res

其中，TreeNode()为自定义的二叉树节点，inorder和postorder是输入的两个列表。最后返回的是二维列表，包含了二叉树的层序遍历序列。

### 回答3：
首先，回想一下二叉树的遍历方式，前序遍历是先访问根节点，然后按照左子树、右子树的顺序递归遍历；中序遍历是先遍历左子树，然后访问根节点，再递归遍历右子树；后序遍历则是先遍历左子树、右子树，然后访问根节点。层序遍历则是从上到下逐层遍历，按照从左至右的顺序访问每个节点。

根据题目要求，已知二叉树的后序遍历和中序遍历，我们需要还原出它的层序遍历。

我们可以使用递归的方式构建二叉树，并同时生成它的层序遍历。由于层序遍历是按照层次遍历的，所以我们可以用一个队列来保存每一层的节点，从队列中取出节点时访问它的左右子节点，并将它们加入队列中，直到队列为空。

具体实现步骤如下：

1. 根据后序遍历和中序遍历还原出二叉树。

后序遍历中最后一个元素为根节点，根据这个元素在中序遍历中的位置可以分出左子树和右子树的中序遍历序列，根据这两个序列的长度可以知道左子树和右子树的后序遍历序列，在递归构建左右子树。

2. 根据二叉树的根节点将它加入队列，并从队列中取出。

3. 访问根节点的左右子节点并将它们加入队列中。

4. 重复步骤2和3，直到队列为空。

最后，队列中的元素就是二叉树的层序遍历序列。

需要注意的是，在还原二叉树时，我们可以使用哈希表来存储中序遍历中每个节点的位置，这样可以减少元素查找的时间复杂度。同时，为了方便构建二叉树，我们可以用数组保存后序遍历序列和中序遍历序列。

实际实现时，我们可以定义一个名为“buildTree”的递归函数，该函数接受四个参数：后序遍历序列、中序遍历序列、每个节点在中序遍历序列中的位置、根节点在后序遍历序列中的位置。该函数返回以根节点为根的子树。

代码如下：

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def build(inorder, postorder, in_start, in_end, post_start, post_end):
            if in_start > in_end:
                return None
            root = TreeNode(postorder[post_end])
            root_idx = idx_map[root.val]
            left_size = root_idx - in_start
            root.left = build(inorder, postorder, in_start, root_idx - 1, post_start, post_start + left_size - 1)
            root.right = build(inorder, postorder, root_idx + 1, in_end, post_start + left_size, post_end - 1)
            return root
        
        n = len(inorder)
        idx_map = {val: idx for idx, val in enumerate(inorder)}
        return build(inorder, postorder, 0, n - 1, 0, n - 1)

接下来是层序遍历的代码：

from collections import deque

def levelOrder(root):
    if not root:
        return []
    queue = deque([root])
    res = []
    while queue:
        level_size = len(queue)
        cur_level = []
        for _ in range(level_size):
            node = queue.popleft()
            cur_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(cur_level)
    return res

最终返回的res即为二叉树的层序遍历序列。

总结一下，本题的关键是如何把已知的后序遍历和中序遍历还原成二叉树，并把还原出的二叉树按照层次遍历输出。通过递归的方式构建二叉树，并使用队列实现层序遍历即可解决。

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

我们可以借助队列实现二叉树的层序遍历。具体步骤如下：

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

2. 初始化一个队列，将根结点入队。

3. 计算队列中的结点个数，依次出队并将其左右子结点入队。

4. 将出队的结点值存入结果列表中。

5. 重复步骤3-4，直到队列为空。

下面是实现的代码：

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

def buildTree(inorder, postorder):
    if not inorder:
        return None
    root_val = postorder[-1]
    root = TreeNode(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

def levelOrder(root):
    if not root:
        return []
    queue = [root]
    res = []
    while queue:
        level_size = len(queue)
        level_nodes = []
        for i in range(level_size):
            node = queue.pop(0)
            level_nodes.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level_nodes)
    return res

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
root = buildTree(inorder, postorder)
print(levelOrder(root))  # Output: [[3], [9, 20], [15, 7]]

时间复杂度：$O(n^2)$。每个节点入队出队各一次，总共需要$n$次操作，每次操作需要计算队列中的结点个数，最坏情况下需要遍历整棵树，因此总时间复杂度为$O(n^2)$。

空间复杂度：$O(n)$。队列中最多同时存储一层的结点，因此空间复杂度为$O(n)$。