#include
#include
#include
using namespace std;
// 定义二叉树的结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
// 根据中序遍历和前序遍历构建二叉树
TreeNode* buildTree(vector& inorder, vector& preorder, int inStart, int inEnd, int preStart, int preEnd) {
if (inStart > inEnd || preStart > preEnd) {
return nullptr;
}
int rootVal = preorder[preStart]; // 前序遍历的第一个结点为根结点
int rootIndex; // 根结点在中序遍历中的索引
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart; // 左子树的结点个数
TreeNode* root = new TreeNode(rootVal);
// 递归构建左子树和右子树
root->left = buildTree(inorder, preorder, inStart, rootIndex - 1, preStart + 1, preStart + leftSize);
root->right = buildTree(inorder, preorder, rootIndex + 1, inEnd, preStart + leftSize + 1, preEnd);
return root;
}
// 将二叉树做镜面反转
void mirrorTree(TreeNode* root) {
if (root == nullptr) {
return;
}
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
mirrorTree(root->left);
mirrorTree(root->right);
}
// 层序遍历二叉树
vector levelOrder(TreeNode* root) {
vector result;
if (root == nullptr) {
return result;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* curr = q.front();
q.pop();
result.push_back(curr->val);
if (curr->left != nullptr) {
q.push(curr->left);
}
if (curr->right != nullptr) {
q.push(curr->right);
}
}
return result;
}
int main() {
int N;
cin >> N;
vector inorder(N);
vector preorder(N);
for (int i = 0; i < N; i++) {
cin >> inorder[i];
}
for (int i = 0; i < N; i++) {
cin >> preorder[i];
}
TreeNode* root = buildTree(inorder, preorder, 0, N - 1, 0, N - 1);
mirrorTree(root);
vector result = levelOrder(root);
for (int i = 0; i < result.size(); i++) {
cout << result[i];
if (i != result.size() - 1) {
cout << ' ';
}
}
return 0;
}