痛定思痛!!我的LCA
从哪里跌倒从哪里爬起来，明年我会再来见你的，亲爱的百度HR。艰苦的路从LCA开始。如何求一棵树中节点的最近公共先祖，Tarjan算法，复杂度O（N）网上说O(N+E)有点不太能理解，基于深度优先搜索和并查集。
算法基本思路，从根开始深度遍历，经过任意一个节点，都要以该节点为根建立一个集合，随着深度遍历的进行，当一个节点的子节点标记被访问时（即该子节点的所有子节点都标记被访问），将该节点所在的集合和该子节点所在的集合合并，并以该节点为根。上述的过程随着深度遍历递归进行。
遍历的过程同时也是查询的过程，当遍历到的节点是其中查询的节点中的一个，判断另一个节点是否已经被访问，如果被标记访问，那LCA就是被访问节点所在集合的根节点。

#include<iostream>#include<string.h>using namespace std;class node{public:int key;bool visit;node* left;node* right;node(){key=-1;visit=false;}~node(){if(this->left!=NULL){delete this->left;this->left=NULL;}if(this->right!=NULL){delete this->right;this->right=NULL;}//delete this;}node(int key){this->key=key;this->left=NULL;this->right=NULL;}};class btree{public:node* root;node* list[10000];btree(){this->root=NULL;}~btree(){delete root;}void insert(node* p){if(p->key<=0)return;if(p->key%2==1)list[(p->key)/2+(p->key)%2-1]->left=p;if(p->key%2==0)list[(p->key)/2+(p->key)%2-1]->right=p;return;}};class union_find_set{public:int anc;int father[10000];union_find_set(){for(int i=0;i<10000;i++)this->father[i]=-1;}int getFather(int v){if(this->father[v]==v){return v;}else{//getFather(this->father[v]);return getFather(father[v]);}}bool same(int x,int y){return (getFather(x)==getFather(y));}bool judge(int x,int y){int fx,fy;fx=getFather(x);fy=getFather(y);if(fx==fy) false;else{father[fx]=fy;return true;}}};union_find_set ufset;int visit[10000];int result;void dfs(node* p,int a,int b){ufset.father[p->key]=p->key;if(a==p->key){if(visit[b]==1)result=ufset.getFather(b);}if(b==p->key){if(visit[a]==1)result=ufset.getFather(a);}if(p->left!=NULL){dfs(p->left,a,b);ufset.judge(p->left->key,p->key);}if(p->right!=NULL){dfs(p->right,a,b);ufset.judge(p->right->key,p->key);}visit[p->key]=1;}void getLCA(node* p,int a,int b){memset(visit,0,sizeof(visit));dfs(p,a,b);}int main(){int a,b;btree* tree=new btree;for(int i=0;i<=14;i++){node* n=new node(i);tree->list[i]=n;tree->insert(n);}tree->root=tree->list[0];//cout<<tree->list[8]->left->key<<endl;while(cin>>a>>b){for(int i=0;i<10000;i++)ufset.father[i]=-1;getLCA(tree->root,a,b);for(int i=0;i<15;i++){//cout<<"father["<<i<<"]="<<ufset.father[i]<<endl;}//cout<<ufset.father[0]<<endl;//cout<<ufset.getFather(3)<<endl;cout<<result<<endl;}delete tree;return 0;}