树中两个结点的最低公共祖先

在进行这个问题之前，我们需要考虑以下几个问题：

（1）题目告诉我们是树，但是没有告诉我们是一棵怎样的树。这里的树可以分为三种结构。第一种：普通的二叉树；第二种：结点中含有指向父亲结点的指针；第三种：二叉搜索树。

（2）对于不同结构的树，处理的方式是不一样的，时间复杂度也是不一样的，我们需要针对每种结构设计解法。

1. 二叉搜索树

二叉搜索树的左子树比根节点小，右子树的值比根节点大，我们可以根据这个性质来考虑这个问题。

我们可以将两个结点分别和根节点做比较，如果两个结点都比根节点小，则在左子树继续比较，反之，则在右子树中继续比较，直到找到一个结点比根节点大或着等于，一个结点比根节点小，则这个根节点就是最低公共祖先。

                                

代码：

struct BinTreeNode
{
	int data;
	BinTreeNode* pLeft;
	BinTreeNode* pRight;
};

class SortBinTree
{
	typedef BinTreeNode TreeNode;
public:
	TreeNode*  FindLowestCommonAnce(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
	{
		if (pRoot == NULL)
			return NULL;
		TreeNode* pCur = pRoot;
		if (pNode1->data > pCur->data&&pNode2->data > pCur->data)
			return  FindLowestCommonAnce(pCur->pRight, pNode1, pNode2);
	
		else if (pNode1->data < pCur->data&&pNode2->data < pCur->data)
		    return  FindLowestCommonAnce(pCur->pLeft, pNode1, pNode2);

		else
			return pCur;

	}
};

2. 含有指向父节点的指针

如果树中含有指向父节点的指针，那么我们可以从最低的叶子结点开始到根节点，看成一条由父节点指向下一个结点的单链表，这样问题就可以转化为求两条单链表的相交结点了。

                               

代码：

template<class T>
struct TreeNode
{
	T data;
	TreeNode* pLeft;
	TreeNode* pRight;
	TreeNode* pParent;
};
template<class T>
class ParentTree
{
	typedef TreeNode<T> TreeNode;
public:
	TreeNode*  FindLowestCommonAnce(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
	{
		if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
			return NULL;
		int count1 = 1;
		int count2 = 1;
		TreeNode* pCur1 = pNode1;
		TreeNode* pCur2 = pNode2;
		while (pCur1->pParent != NULL)
		{
			count1++;
			pCur1 = pCur1->pParent;
		}
		while (pCur2->pParent != NULL)
		{
			count2++;
			pCur2 = pCur2->pParent;
		}
		int Lengthdif = count1 - count2;
		TreeNode* pLong = pNode1;
		TreeNode* pShort = pNode2;
		if (count1 < count2)
		{
			pLong = pNode2;
			pShort = pNode1;
			Lengthdif = count2 - count1;
		}
		for (int i = 0; i < Lengthdif; i++)
		{
			pLong = pLong->pParent;
		}
		while (pLong != NULL&&pShort != NULL&&pLong != pShort)
		{
			pLong = pLong->pParent;
			pShort = pShort->pParent;
		}
		TreeNode* pFirst = pLong;
		return pFirst;
	}
	
};

3. 普通二叉树

普通二叉树相比之下有点难，不过我们可以将第二种方法变换一下，从根节点开始向下遍历，并将遍历到的结点保存在某一容器中，这样就形成了一条到指定结点的路径，然后根据两个结点的路径找相同的结点，这个相同的结点就是最低公共祖先。

                           

代码：

template<class T>
class Tree
{
public:
	TreeNode*  FindLowestCommonAnce(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
	{
		if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
			return NULL;
		list<TreeNode*> path1;
		GetNodepath(pRoot, pNode1, path1);
		list<TreeNode*> path2;
		GetNodepath(pRoot, pNode2, path2);

		list<TreeNode*>::const_iterator iterator1 = path1.begin();
		list<TreeNode*>::const_iterator iterator2 = path2.begin();
		TreeNode* pLast = NULL;
		while (iterator1 != path1.end() && iterator2 != path2.end())
		{
			if (*iterator1 == *iterator2)
				pLast = *iterator1;

			iterator1++;
			iterator2++;
		}
		return pLast;
	}
	bool GetNodepath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>&path)
	{
		if (pRoot == pNode)
			return true;
		path.push_front(pRoot);
		bool found = false;
		found = GetNodepath(pRoot->pLeft, pNode, path);

		if (!found)
			found = GetNodepath(pRoot->pRight, pNode, path);

		if (!found)
			path.pop_front(pRoot);
		return found;
	}
};

第二种方式：

template<class T>
class Tree
{
	typedef TreeNode<T> TreeNode;
public:
	TreeNode*  FindLowestCommonAnce(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
	{
		if (pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
			return NULL;
		if (IsInTheBinaryTree(pRoot->pLeft, pNode&&\
			IsInTheBinaryTree(pRoot->pLeft, pNode2))
			return  FindLowestCommonAnce(pRoot->pLeft, pNode1, pNode2);
		else if (IsInTheBinaryTree(pRoot->pRight, pNode&&\
			IsInTheBinaryTree(pRoot->pRight, pNode2))
			return  FindLowestCommonAnce(pRoot->pRight, pNode1, pNode2);
		else
			return pRoot;
	}
	bool IsInTheBinaryTree(TreeNode* root,TreeNode* n)
	{
		
		if (root == n)
			return true;
		bool found = IsInTheBinaryTree(root->left, n);
		if (!found)
			found = IsInTheBinaryTree(root->right, n);
		return found;
	}
};