PTA二叉搜索树的最近公共祖先
给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 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.。
输入样例：
6 86 3 1 2 5 4 8 72 58 71 912 -30 899 99输出样例：
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代码：
#includeusing namespace std;int a[10005];//存储n和键值sets;void ju(int l,int r,int x,int y){//判断x和y是不是分别位于以a[l]为根的左子树和右子树中//是的话，则a[l]是x与y的最近公共祖先。否则递归往下找。if(a[l]==x) printf("%d is an ancestor of %d.\n",x,y);//x是y的祖先else if(a[l]==y) printf("%d is an ancestor of %d.\n",y,x);//y是x的祖先else if((x=a[l])||(y=a[l]))//分别位于以a[l]为根的左右子树 printf("LCA of %d and %d is %d.\n",x,y,a[l]);else{int i; for(i=l;i<r&&a[i]<a[l];i++);//找左右子树的分界点 if(x<a[l]&&y=a[l]&&y>=a[l])// 都在右子树 ju(i+1,r,x,y); } }int main(){int m,n;cin>>m>>n;for(int i=1;i>a[i];s.insert(a[i]);}while(m--){int u,v,f1=0,f2=0;cin>>u>>v;if(s.find(u)==s.end()) f1=1;if(s.find(v)==s.end()) f2=1;if(f1+f2==2) printf("ERROR: %d and %d are not found.\n",u,v);else if(f1==1) printf("ERROR: %d is not found.\n",u);else if(f2==1) printf("ERROR: %d is not found.\n",v);else ju(1,n,u,v);} return 0;}