[C++] PAT 1143 Lowest Common Ancestor (30分)
程序员文章站
2022-07-14 14:51:19
...
Sample Input:
6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99
Sample Output:
LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.
题解:
根据BST的特性,
对于输入u,v,可以观察a是否是属于[u,v]范围,
若是,则a就是u,v的最小公共祖先,
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
map<int,bool> mp;
int n,m;
vector<int> arr;
int main(){
cin >> n >>m;
arr.resize(m);
for(int i=0;i<m;i++){
scanf("%d",&arr[i]);
mp[arr[i]] = true;
}
int u,v;
int a;
for(int i=0;i<n;i++){
cin >> u >> v;
for(int j=0;j<arr.size();j++){
a = arr[j];
if(a>v && a<u || a>u && a<v || a==v || a==u) break;
}
if(mp[u]==false && mp[v]==false){
printf("ERROR: %d and %d are not found.\n",u,v);
}
else if(mp[u]==false || mp[v]==false){
printf("ERROR: %d is not found.\n",mp[u]==false?u:v);
}
else if( a>v && a<u || a>u && a<v){
printf("LCA of %d and %d is %d.\n",u,v,a);
}
else if(a==v || a==u){
printf("%d is an ancestor of %d.\n",a == u?u:v,a == u? v:u);
}
}
system("pause");
return 0;
}
上一篇: 树中两个节点的最近公共祖先 多种情况分析
下一篇: 二元分类问题搭建逻辑回归模型
推荐阅读
-
PAT甲级1143 Lowest Common Ancestor BST+LCA
-
1143 Lowest Common Ancestor 甲级
-
[C++] PAT 1143 Lowest Common Ancestor (30分)
-
⭐⭐⭐⭐⭐PAT A1143 Lowest Common Ancestor
-
PAT 1143 Lowest Common Ancestor 【C++版】
-
1143 Lowest Common Ancestor
-
pat-1143 Lowest Common Ancestor (30分)
-
1143 Lowest Common Ancestor (30分)
-
1143 Lowest Common Ancestor (30分)
-
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree C++