玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

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

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

解题代码：

include

include

include <unordered_map>

include

using namespace std;

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

unordered_map<int, int> pos;

// 递归构建二叉树
TreeNode* build(vector& in, vector& pre, int inL, int inR, int preL, int preR) {
if (inL > inR || preL > preR) return nullptr;
int rootVal = pre[preL];
TreeNode* root = new TreeNode(rootVal);
int k = pos[rootVal];
int leftSize = k - inL;
root->left = build(in, pre, inL, k-1, preL+1, preL+leftSize);
root->right = build(in, pre, k+1, inR, preL+leftSize+1, preR);
return root;
}

// 层序遍历（先右后左，等价于镜面反转后的层序）
vector levelOrderReverse(TreeNode* root) {
vector res;
if (!root) return res;
queue<TreeNode> q;
q.push(root);
while (!q.empty()) {
TreeNode node = q.front();
q.pop();
res.push_back(node->val);
// 先加右孩子，再加左孩子，实现镜面反转的层序
if (node->right) q.push(node->right);
if (node->left) q.push(node->left);
}
return res;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
cin >> n;
vector<int> in(n), pre(n);
for (int i = 0; i < n; ++i) {cin >> in[i];pos[in[i]] = i;
}
for (int i = 0; i < n; ++i) cin >> pre[i];TreeNode* root = build(in, pre, 0, n-1, 0, n-1);
vector<int> ans = levelOrderReverse(root);// 输出结果
for (int i = 0; i < ans.size(); ++i) {if (i > 0) cout << " ";cout << ans[i];
}
cout << endl;return 0;

}

二叉树的相关知识，接下来一周都会是二叉树，会慢慢说知识点