痛定思痛!!我的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;
}