L2-011 玩转二叉树

L2-011传送门

这道题与前面的一道题几乎一样😁(*^▽^*)

唯一有变化的就是镜像翻转

1. 那我们只需要先建右子树，再建左子树就行了。
2. 或者我们可以正常建树，但是在BFS的时候 ， 先让右边入队，再让左边入队。
   你会选择哪一个呢？

实际上，选择第一点最好，因为第二点并没有真正的建树，很多时候，我们必须要在内存上做出改变才行啊。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>using namespace std;int pre[10010], in[10010];
unordered_map<int, int> l, r, pos;int build(int inL, int inR, int preL, int preR)
{if (inL > inR) {return -1;}int root = pre[preL];int k = pos[root];int num = k - inL;// 【核心翻转逻辑】// 原本 build(inL, k - 1, ...) 是左子树，现在赋值给 r[root]// 原本 build(k + 1, inR, ...) 是右子树，现在赋值给 l[root]// 这样在树的物理结构上，左右就彻底颠倒了r[root] = build(inL, k - 1, preL + 1, preL + num);l[root] = build(k + 1, inR, preL + num + 1, preR);return root;
}void bfs(int root)
{if (root == -1) return;queue<int> q;q.push(root);bool first = true;while (!q.empty()){int now = q.front();q.pop();if (!first) cout << " ";cout << now;first = false;// 既然建树时已经翻转，这里依然按照标准【先左后右】入队// 此时输出的就是镜像后的层序if (l.count(now) && l[now] != -1) q.push(l[now]);if (r.count(now) && r[now] != -1) q.push(r[now]);}
}int main()
{int n;cin >> n;for (int i = 0; i < n; i++) cin >> in[i];for (int i = 0; i < n; i++){cin >> pre[i];pos[pre[i]] = i; // 报错预警：注意这里应该是记录中序的下标，即 pos[in[i]] = i}// 严密修正：记录中序下标for (int i = 0; i < n; i++) pos[in[i]] = i;int root = build(0, n - 1, 0, n - 1);bfs(root);cout << endl;return 0;
}