目的：找到两个节点的最低祖先。在二叉搜索树上找

输入：

M  被测试的节点对数 1000

N  二叉搜索树的节点个数 10000

然后给出二叉搜索树的先序遍历序列

然后再是M个节点对。每对节点有U,V两个节点。

输出：

如果找到了LCA，输出"LCA of U and V is A."

如果LCA是U和V中的一个，输出"X is an ancestor of Y."

如股票没有找到：

可能是因为点不在树中；

输出：ERROR: U is not found. 

           ERROR: V is not found. 

           ERROR: U and V are not found.

算法：

根据二叉搜索树的特点，若是两个节点的最小根节点。那么这个节点的值一定处于两个之间，而且，一定在两个节点之前。

判断在不在树中，用一个map存一下，查找看在不在。

#include<stdio.h>
#include<map>
#include<math.h>using namespace std;const int maxn = 10010;
int a[maxn];
map<int,int> b;
int n,m;int main()
{scanf("%d%d",&m,&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);b[a[i]] = 1;}for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);if(b.find(u)==b.end()&&b.find(v)==b.end()){printf("ERROR: %d and %d are not found.\n",u,v);}else if(b.find(u)==b.end()){printf("ERROR: %d is not found.\n",u);}else if(b.find(v)==b.end()){printf("ERROR: %d is not found.\n",v);}else{int ans;for(int j=0;j<n;j++){if(a[j]>min(u,v)&&a[j]<=max(u,v)){ans = a[j];break;}}if(ans==u||ans==v){printf("%d is an ancestor of %d.\n",ans,ans==u?v:u);}else{printf("LCA of %d and %d is %d.\n",u,v,ans);}}}return 0;
}

反思：最后一些困难，是狭隘得理解了根节点一定在中间，所以我认为，根节点一定大于左边节点，小于等于右边节点，事实上，这两个节点中可能有根节点，所以两边都有等于。