// 包含所需的头文件
#include
#include
#include <unordered_map>
using namespace std;
// 定义二叉树节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 构建二叉树的函数，根据中序遍历和后序遍历构建二叉树
TreeNode* buildTree(vector& inorder, vector& postorder, int in_start, int in_end, int post_start, int post_end, unordered_map<int, int>& map) {
// 如果中序遍历的起始位置大于结束位置，或者后序遍历的起始位置大于结束位置，说明已经没有节点可以构建二叉树了，返回NULL
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 = 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, map);
root->right = buildTree(inorder, postorder, root_index + 1, in_end, post_start + left_size, post_end - 1, map);
return root;
}
// 层序遍历二叉树的函数
vector levelorderTraversal(TreeNode* root) {
vector result;
// 如果二叉树为空，直接返回空结果
if (root == NULL) {
return result;
}
// 创建一个队列，用于存储待遍历的节点
queue<TreeNode*> q;
// 将根节点入队
q.push(root);
// 循环遍历队列中的节点
while (!q.empty()) {
// 取出队列中的节点
TreeNode* node = q.front();
q.pop();
// 将节点的值加入结果数组
result.push_back(node->val);
// 如果节点有左子节点，将左子节点入队
if (node->left != NULL) {
q.push(node->left);
}
// 如果节点有右子节点，将右子节点入队
if (node->right != NULL) {
q.push(node->right);
}
}
return result;
}
int main() {
// 输入节点个数
int N;
cin >> N;
// 创建存储后序遍历和中序遍历的数组
vector postorder(N);
vector inorder(N);
// 创建一个哈希表，用于存储中序遍历数组中每个节点的索引
unordered_map<int, int> map;
// 输入后序遍历数组
for (int i = 0; i < N; i++) {
cin >> postorder[i];
}
// 输入中序遍历数组，并将每个节点的值和索引存入哈希表中
for (int i = 0; i < N; i++) {
cin >> inorder[i];
map[inorder[i]] = i;
}
// 构建二叉树
TreeNode* root = buildTree(inorder, postorder, 0, N - 1, 0, N - 1, map);
// 层序遍历二叉树，并输出结果
vector levelorder = levelorderTraversal(root);
for (int i = 0; i < levelorder.size(); i++) {
cout << levelorder[i];
if (i != levelorder.size() - 1) {
cout << ' ';
}
}
return 0;
