1143 Lowest Common Ancestor
这道题目考查的是BST建树 + 离散化 + LCA
BST建树
首先BST建树与之前不同的是:之前需要记录的是一个结点的左右子树,而本次需要记录的是父结点,以及该结点的深度。
离散化
虽然STL自带哈希表unordered_map
,但是该哈希表的常数比较大,容易超时。所以需要把值映射到数组中。因为数组的访问要相比较于哈希表要快得多。
(1)将所以的数读入到seq序列,然后将其排序。即将seq[i] 映射为 i。
(2)由于BST的中序遍历是不减序列,所以in[i] = i
。而pos[i]
需要通过一个哈希表pos辅助查询。
(3)这样对于p[i]
和depth[i]
都可以直接用下标进行操作。
(4)在最后询问的过程中,由于输入是原值,所以首先需要映射为下标之后才能够进行判断。输出还需从下标再转化为原值。
相较于哈希表unordered_map
:对于中序遍历的k值查找,p数组和depth数组访问都能转化为数组的访问,时间效率大大提升。
LCA思路:
(1)任意两个树中的结点都一定有LCA。(最次就是根节点)
(2)因为最后的结点为一个点(depth[i]
相同),所以通过将两个结点不断爬升,判断两个结点是否相等来寻找LCA。
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int M = 1010, N = 10010;
int m, n;
int pre[N], in[N], seq[N];
int p[N], d[N];
unordered_map<int,int> pos;
int build(int il, int ir, int pl, int pr, int depth)
{
int root = pre[pl];
int k = root;
// p和d数组直接对下标进行操作
d[root] = depth;
if(k>il) p[build(il,k-1,pl+1,pl+1+k-1-il,depth+1)] = root;
if(ir>k) p[build(k+1,ir,pl+1+k-1-il+1,pr,depth+1)] = root;
return root;
}
int main()
{
cin >> m >> n;
for(int i = 0; i < n; i ++ )
{
cin >> pre[i];
seq[i] = pre[i];
}
sort(seq, seq + n);
for(int i = 0; i < n; i ++ )
{
// pos[原值] = 映射后的下标
pos[seq[i]] = i;
// 中序遍历不减,直接为i
in[i] = i;
}
for(int i = 0; i < n; i ++ ) pre[i] = pos[pre[i]]; // 先序遍历需要哈希表辅助查找
build(0, n - 1, 0, n - 1, 0);
while(m -- ){
int a, b;
scanf("%d%d", &a, &b);
if(pos.count(a) && pos.count(b)){
// 需要先转化为下标
int x = pos[a], y = pos[b];
while(x != y){
if(d[x] > d[y]) x = p[x];
else y = p[y];
}
// 输出再转化为原值
x = seq[x];
if(x != a && x != b)
printf("LCA of %d and %d is %d.\n",a,b,x);
else if(x != a)
printf("%d is an ancestor of %d.\n",b,a);
else
printf("%d is an ancestor of %d.\n",a,b);
}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 if(pos.count(b) == 0){
printf("ERROR: %d is not found.\n",b);
}
}
return 0;
}