题目描述
给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。
输入
输入的第一行给出两个正整数：待查询的结点对数 M（≤ 1 000）和二叉搜索树中结点个数 N（≤ 10 000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M 行，每行给出一对整数键值 U 和 V。所有键值都在整型int范围内。
输出
对每一对给定的 U 和 V，如果找到 A 是它们的最近公共祖先结点的键值，则在一行中输出 LCA of U and V is A.。但如果 U 和 V 中的一个结点是另一个结点的祖先，则在一行中输出 X is an ancestor of Y.，其中 X 是那个祖先结点的键值，Y 是另一个键值。如果 二叉搜索树中找不到以 U 或 V 为键值的结点，则输出 ERROR: U is not found. 或者 ERROR: V is not found.，或者 ERROR: U and V are not found.。
输入样例1
6 8 6 3 1 2 5 4 8 7 2 5 8 7 1 9 12 -3 0 8 99 99
输出样例1
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.
AC代码
代码语言：javascript复制#include<iostream>
#include<set>
#include<map>
using namespace std;
struct Node {
int data;
Node *left = NULL;
Node *right = NULL;
};
class BST {
map<int,int>ancestor;
public:
Node *root = NULL;
void Insert(int &data) {
Node *newOne = new Node();
newOne->data = data;
if (root == NULL) {
root = newOne;
return;
}
Node *current = root;
while (current) {
if (current->data > data) {
if (current->left)
current = current->left;
else {
current->left = newOne;
ancestor[data]=current->data;
return;
}
} else {
if (current->right)
current = current->right;
else {
current->right = newOne;
ancestor[data]=current->data;
return;
}
}
}
}
bool IsAncestor(int&a,int&b){
for(auto&[child,parent]:ancestor)
if(child==a&&parent==b){
cout<<b<<" is an ancestor of "<<a<<'.'<<endl;
return true;
}else if(child==b&&parent==a){
cout<<a<<" is an ancestor of "<<b<<'.'<<endl;
return true;
}
return false;
}
int FindBingo(int&a,int&b,Node*current){
if(a>current->data&&b>current->data)
return FindBingo(a,b,current->right);
else if(a<current->data&&b<current->data)
return FindBingo(a,b,current->left);
return current->data;
}
};
int main() {
int m,n, temp,U,V;
BST test;
set<int>data;
cin >>m>> n;
while (n--) {
cin >> temp;
data.insert(temp);
test.Insert(temp);
}
while(m--){
cin>>U>>V;
if(data.find(U)==data.end()&&data.find(V)==data.end()){
cout<<"ERROR: "<<U<<" and "<<V<<" are not found."<<endl;
continue;
}else if(data.find(U)==data.end()){
cout<<"ERROR: "<<U<<" is not found."<<endl;
continue;
}else if(data.find(V)==data.end()){
cout<<"ERROR: "<<V<<" is not found."<<endl;
continue;
}else if(test.IsAncestor(U,V))
continue;
temp=test.FindBingo(U,V,test.root);
if(temp==U){
cout<<U<<" is an ancestor of "<<V<<'.'<<endl;
}else if(temp==V){
cout<<V<<" is an ancestor of "<<U<<'.'<<endl;
}else
cout<<"LCA of "<<U<<" and "<<V<<" is "<<temp<<'.'<<endl;
}
return 0;
}
