一、题目描述
原题链接
Input Specification:
??Output Specification:
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的LCA，有一个有趣的结论是可以记一下的，就是先序遍历中的第一个在这两个数的范围之间的数就是它们的LCA，根据这个结论，代码就很容易写了。
三、AC代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> tree;
int main()
{
int M, N, tmp;scanf("%d%d", &M, &N);for(int i=0; i<N; i++){
scanf("%d", &tmp);tree.push_back(tmp);}int a, b, sze = tree.size();for(int i=0; i<M; i++){
bool ina = false, inb = false;scanf("%d%d", &a, &b);for(int k=0; k<sze; k++){
if(tree[k] == a) ina = true;if(tree[k] == b) inb = true;}if(ina && inb){
for(int j=0; j<sze; j++){
if(tree[j] >= min(a, b) && tree[j] <= max(a, b)){
if(tree[j] == max(a, b)){
printf("%d is an ancestor of %d.\n", max(a, b), min(a, b));break;}else if(tree[j] == min(a, b)){
printf("%d is an ancestor of %d.\n", min(a, b), max(a, b));break;}else{
printf("LCA of %d and %d is %d.\n", a, b, tree[j]);break;}}}}else{
if(ina) printf("ERROR: %d is not found.\n", b);else if(inb) printf("ERROR: %d is not found.\n", a);else printf("ERROR: %d and %d are not found.\n", a, b);}}return 0;
}