二叉树两个结点的最低共同父结点

ゞ浴缸里的玫瑰 2022-08-08 00:58 128阅读 0赞

入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。  
分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至  
少有两个变种。  
第一变种是二叉树是一种特殊的二叉树：查找二叉树。也就是树是排序过的，位于  
左子树上的结点都比父结点小， 而位于右子树的结点都比父结点大。 我们只需要从根结点开  
始和两个结点进行比较。 如果当前结点的值比两个结点都大， 则最低的共同父结点一定在当  
前结点的左子树中。 如果当前结点的值比两个结点都小， 则最低的共同父结点一定在当前结  
点的右子树中。  
第二个变种是树不一定是二叉树，每个结点都有一个指针指向它的父结点。于是我  
们可以从任何一个结点出发， 得到一个到达树根结点的单向链表。 因此这个问题转换为两个

单向链表的第一个公共结点。

思路：现在我们回到这个问题本身。所谓共同的父结点，就是两个结点都出现在这个结点  
的子树中。假如我们从头部开始遍历，一旦发现有节点和两个节点中的一个相等，那么此节点就是目标节点，要么公共父节点在左子树，要么在右子树。如果发现两个节点一个在左子树，一个在右子树，那么当前节点就是公共父节点，如果发现有都在右子树，那么公共父节点就在右子树，如果发现都在左子树，那么公共父节点在右子树

bool FindNode(BinTree* root,BinTree* node)
    {
    	if(root == NULL)
    		return false;
    	if(root == node)
    		return true;
    	return (FindNode(root->left,node) ||FindNode(root->right,node));
    }
    BinTree* LCP(BinTree* root,BinTree* first,BinTree* second)
    {
    	if(root == first || root == second)
    		return root;
    	bool isLeft = false;
    	isLeft = FindNode(root->left,first);
    	if(isLeft)
    	{
    		if(FindNode(root->left,second))
    			return LCP(root->left,first,second);
    		else
    			return root;
    	}
    	else
    	{
    		if(FindNode(root->right,second))
    			return LCP(root->right,first,second);
    		else
    			return root;
    	}
    }

另一种实现：

/*
    求二叉树中两个节点的最低公共祖先节点
    */
    
    BinTree* LCA(BinTree* root,BinTree* first,BinTree* second)
    {
    	if(root == first || root == second )
    		return root;
    	if(root == NULL)
    		return NULL;
    	BinTree* left = LCA(root->left,first,second);
    	BinTree* right = LCA(root->right,first,second);
    	if(left == NULL)
    		return right;
    	else if(right == NULL)
    		return left;
    	else
    		return root; 
    }

其实找最低公共祖先这个题目还是很有意思的，从第二种实现来看，我们可以思考一个问题，假如这两个节点有公共祖先的话，那么如果当前的节点和两个节点中的一个相同，那么说明当前节点就是公共祖先，如果都不相同，那么按理来说应该由更加低级别的公共祖先，我们尝试着再往低的级别找公共祖先，（注意这个时候仍然不排除当前节点是两个节点的公共祖先），我们从左子树和右子树都查找更加低的公共祖先，如果在左子树没有找到，那么就返回在右子树查找的结果，这个时候如果右子树又结果，那么它的结果就是最低公共祖先，如果在右子树中没有找到，那么说明这两个节点没有最低公共祖先。

如果左子树查找到了结果。left != NULL,那么就看一下right是否为NULL，如果right != NULL 那么说明在左右两个子树中都查找到了公共祖先，那么说明最低的公共祖先就是当前的节点！

三、也可以使用最原始的这种方法

既然让找最低的公共祖先，那么我们就分别从根节点找两个节点的路径，两天路径中从前往后看，最后一个相同的几点就是最低公共祖先。淡然找路径的问题就是回溯剪枝问题。这种解决方法在后续的某篇文章中有介绍。

我们再看分析一下这个题目，第一次看到这个题目可能无从下手，但是慢慢琢磨一下，最低的公共祖先，如果当前节点和其中的两个中的某一个相同，那么就是当前祖先，然后再判断左子树中是否有其中的某一个节点，然后根据这个结果就可以进行下面的操作。也就是本篇文章中第一宗解决方法。第三种解决方法就是不使用递归的方法。