题意
给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。
Input
输入的第一行给出两个正整数：待查询的结点对数 M（≤ 1000）和二叉搜索树中结点个数 N（≤ 10000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M行，每行给出一对整数键值 U和 V。所有键值都在整型int范围内。
Output
对每一对给定的 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。
思路
难点在于建树
二叉搜索树性质：左儿子的值<根节点的值<右儿子的值，所以中序遍历是递增的序列。
题目给出了先序遍历，那么从小到大排序后就是中序遍历，建树的过程位根据先序遍历和中序遍历建立二叉树。
递归建树后，根据二叉搜索树的性质递归查找lca的值。如果x,y都大于当前节点的值，说明x,y都在当前节点的右子树；如果x,y都小于当前节点的值，说明x,y都在当前节点的左子树；否则，说明x,y分列在当前节点的左、右子树，那么当前节点就是lca。
代码
#include <bits/stdc++.h> using namespace std; const int maxn=1e4+100; #define debug(x) cout<<#x<<":"<<x<<endl; struct node{ int val; node *l; node *r; }; node tr[maxn]; int a[maxn],b[maxn],idx; map<int,int>mp; node* build(int len,int u,int st){ if(len<1) return 0; node* now=&tr[idx++];///根节点 now->val=a[u]; int t=0; t=lower_bound(b+t+st,b+len+st,a[u])-b-st;///找到根节点 /// debug(t); now->l=build(t,u+1,st); now->r=build(len-t-1,u+t+1,st+t+1); return now; } int lca(int x,int y,node* root){ if(x>root->val&&y>root->val) return lca(x,y,root->r); else if(x<root->val&&y<root->val) return lca(x,y,root->l); else return root->val; } int main() { int m,n;cin>>m>>n; for(int i=0;i<n;i++){ cin>>a[i]; ///debug(a[i]); b[i]=a[i]; mp[b[i]]=1;///标记出现过 } sort(b,b+n);///中序遍历 node* root=build(n,0,0); while(m--){ int x,y; cin>>x>>y; if(!mp.count(x)&&!mp.count(y)) printf("ERROR: %d and %d are not found.\n",x,y); else if(!mp.count(x)&&mp.count(y)) printf("ERROR: %d is not found.\n",x); else if(mp.count(x)&&!mp.count(y)) printf("ERROR: %d is not found.\n",y); else{ int par=lca(x,y,root); if(par==x){ printf("%d is an ancestor of %d.\n",x,y); } else if(par==y){ printf("%d is an ancestor of %d.\n",y,x); } else{ printf("LCA of %d and %d is %d.\n",x,y,par); } } } return 0; }
