欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-14 14:49:15
...

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

(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;
	}
};