离散化的理解
如何离散化,只能离散化中序遍历,不能离散化其他遍历 ,因为从遍历构建树,本质上是寻找根在中序遍历的位置。
(故其实都无需存储中序遍历序列,只需存储中序遍历位置。)
错的eg。
for:
cin >> pre[i];
pos[pre[i]]=i;
pre[i]=i;
for:
cin >> in[i];
in[i]=pos[in[i]];
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int p[N], d[N];
unordered_map<int, int> pos;
int in[N], pre[N], sq[N];
int build(int il, int ir, int pl, int pr, int dep) {
int rt=pre[pl];
int k=rt;
d[rt]=dep;
if(k>il) p[build(il, k-1, pl+1, pl+1+k-1-il, dep+1)]=rt;
if(k<ir) p[build(k+1, ir, pl+1+k-il, pr, dep+1)]=rt;
return rt;
}
int main() {
int n, m;
cin >> m >> n;
for(int i=0; i<n; i++) {
cin >> sq[i];
pos[sq[i]]=i;
in[i]=i;
}
for(int i=0; i<n; i++) {
cin >> pre[i];
pre[i]=pos[pre[i]];
}
build(0, n-1, 0, n-1, 0);
while(m--) {
int a, b;
cin >> a >> b;
if(pos.count(a) && pos.count(b)) {
a=pos[a], b=pos[b];
int x=a, y=b;
while(a!=b) {
if(d[a]>=d[b]) a=p[a];
else b=p[b];
}
if(a!=x && b!=y) printf("LCA of %d and %d is %d.\n", sq[x], sq[y], sq[a]);
else if(a==x) printf("%d is an ancestor of %d.\n", sq[x], sq[y]);
else printf("%d is an ancestor of %d.\n", sq[y], sq[x]);
} else if(pos.count(a)==0 && pos.count(b)==0)
printf("ERROR: %d and %d are not found.\n", a, b);
else if(pos.count(a)==0)
printf("ERROR: %d is not found.\n", a);
else printf("ERROR: %d is not found.\n", b);
}
return 0;
}