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

面试题50_树中两个节点的最低公共祖先

程序员文章站 2022-07-03 19:18:31
...

面试题50_树中两个节点的最低公共祖先

1、关于问题的转化流程:

树——二叉树(排序二叉树)——二叉树(普通二叉树,但是节点中含有指向父节点的指针)——普通的树。


2、如果是这课树是二叉树,并且是排序二叉树,是可以找到给定两个结点的最低公共祖先的。

直观思路:排序二叉树是排序过的,位于左子树的结点值都比父节点小,位于右子树的结点值都比父节点大。

那么,我们只需要从排序二叉树的根节点开始和输入的两个结点进行比较。

如果当前结点的值比两个结点的值都大,那么最低的公共祖先肯定在当前结点的左子树中,于是下一步遍历当前结点的左子树即可。如果当前结点的值比两个结点的值都小,那么最低的公共祖先肯定在当前结点的右子树中,于是下一步遍历当前结点的右子树即可。这样,在树中从上到下找到的第一个在两个给定结点的值之间的结点,就是我们寻求第一个公共最先结点。


3、如果这棵树不是排序二叉树,只是一棵普通的二叉树而已,但是每个结点都存在指向父结点的指针,也是可以找到给定两个结点的最低公共祖先的。

直观思路:如果每个结点都存在指向父节点的指针,那么这个问题可以转化为寻求两个单链表的第一个公共结点。

假设树节点中指向父节点的指针是pParent,那么从树的每一个叶子节点到树的根节点都存在一条由指针pParent 连接起来的单链表。

输入两个结点,那么这两个结点位于两个链表上,它们的最低公共祖先刚好就是这两个单链表的第一个公共结点。

比如输入的两个结点分别是:F 和 H。则F 结点位于单链表:F—D—B—A;H 结点位于单链表:H—E—B—A。

所有它们的第一个公共结点B 就是它们的最低公共祖先。


4、现在假设这棵树是普通的二叉树,没有指向父节点的指针,其实是可以找到给定两个结点的最低公共祖先的。

直观思路:我们首先得到一条从根节点到树中某一节点的路径,这就要求我们在遍历的时候,需要有一个辅助内存来保存路径。比如,我们用前序遍历的方式来得到从根节点到 H 结点的路径过程是这样的:

(1)先遍历根节点A,把A 存放到路径中去,现在路径中有一个节点A ;

(2)遍历到B,把B 存放到路径中去,此时路径为A——B;

(3)遍历到D,把D 存放到路径中去,此时路径为A——B——D;

(4)遍历到F,把F 存放到路径中去,此时路径为A——B——D——F;

(5)F 已经没有子节点了,因此这条路径不可能到达结点H。于是把F 从路径中删除掉,变成A——B——D;

(6)遍历D 的右孩子G,和节点F 一样,这条路径也不能到达H。遍历完G 之后,路径仍然是A——B——D;

(7)由于D 的所有子节点都遍历完了,不可能通过D 达到结点H,所有D 不在从A 到H 的路径中,所有删除D,变成A——B;

(8)遍历E,把E 加入到路径中去,此时路径变成A——B——E;

(9)遍历H,发现已经达到目标结点,A——B——E;就是根节点到H 结点必须经过的路径。

同样的,我们按照这种方法再得到另外一个条指定节点的路径A——B——D;接着,我们求出它们的最后一个公共结点B,也就是F 和H 的最低公共祖先。


时间复杂度:两次遍历树,每一次遍历的时间复杂度都是O(n)。

空间复杂度:得到的路径最差情况是O(n),普通情况两条路径的长度是O(logN)。


最难的是题4的代码,如下:

//题目4
#include<iostream>
#include<list>
using namespace std;
struct BiTree
{
	int value;
	BiTree *pLeft;
	BiTree *pRight;
	BiTree(int x):value(x),pLeft(nullptr),pRight(nullptr) {}
};
//得到指定节点的路径
bool GetNodePath(BiTree *pRoot, BiTree *pNode, list<BiTree *> &path)
{
	if(pRoot==nullptr || pNode==nullptr)
		return false;
	path.push_back(pRoot);
	bool found=false;
	if(pRoot==pNode)
	{
		found=true;
		return found;
	}
	if(!found && pRoot->pLeft)
		found=GetNodePath(pRoot->pLeft,pNode,path);
	if(!found && pRoot->pRight)
		found=GetNodePath(pRoot->pRight,pNode,path);
	if(!found)
		path.pop_back();
	return found;
}
//得到两条路径的最后公共节点
BiTree *GetLastCommomNode(const list<BiTree *> path1, const list<BiTree *> path2)
{
	list<BiTree *>::const_iterator iterator1=path1.cbegin();
	list<BiTree *>::const_iterator iterator2=path2.cbegin();
	BiTree *pLast=nullptr;
	while(iterator1 != path1.cend() && iterator2 != path2.cend())
	{
		if(iterator1 == iterator2)
			pLast=*iterator1;
		++iterator1;
		++iterator2;
	}
}

//综合起来的函数
BiTree *GetLastCommomNodeParent(BiTree *pRoot, BiTree *pNode1, BiTree *pNode2)
{
	if(pRoot==nullptr || pNode1==nullptr || pNode2==nullptr)
		return nullptr;
	list<BiTree *> path1;
	list<BiTree *> path2;
	GetNodePath(pRoot,pNode1,path1);
	GetNodePath(pRoot,pNode2,path2);
	return GetLastCommomNode(path1,path2);
}