首页 > 代码库 > 019写程序在一棵二叉树中找到两个结点的最近共同祖先（keep it up)

019写程序在一棵二叉树中找到两个结点的最近共同祖先（keep it up)

2024-07-21 11:44:58   220人阅读

写程序在一棵二叉树中找到两个结点的最近共同祖先。
分两种情况来讨论这个题：
第一种情况结点中没有指向父结点的指针
第二种情况接种有指向父节点的指针


我们先看第一种情况，结点中没有指向父结点的指针。
我们可以采用暴力搜索每一个结点，如果这个结点的子树中
有已知的两个结点，那我们就继续沿着左右子树找，如果左子树
能找到，我们就继续沿着左子树找，如果有子树能找到，我们就

沿着右子树找，不存在两个子树都能够找到。

代码：

struct TreeNode
{<pre name="code" class="html">struct TreeNode
{
	int data;
	TreeNode* leftChild;
	TreeNode* rightChild;
	TreeNode* parent;
};

//用父结点
bool findNearestAncestor2(const TreeNode* vNodeA, const TreeNode* vNodeB, TreeNode *vAncestor)
{
	if (isFather(vNodeA, vNodeB))
	{
		vAncestor = vNodeA;
		return true;
	}

	if (isFather(vNodeB, vNodeA))
	{
		vAncestor = vNodeB;
		return true;
	}

	TreeNode* Parent = vNodeA->parent;
	while (true)
	{
		if (isFather(Parent, vNodeB))
		{
			vAncestor = Parent;
			return true;
		}
		Parent = Parent->parent;
	}
	return false;
}



在看第二种情况比较简单，如果有指向父结点的指针，我们可以搜索第一个结点的
父节点，然后判断是不是第二个已知结点的父结点。

代码：


struct TreeNode
{
	int data;
	TreeNode* leftChild;
	TreeNode* rightChild;
	TreeNode* parent;
};

//用父结点
bool findNearestAncestor2(const TreeNode* vNodeA, const TreeNode* vNodeB, TreeNode *vAncestor)
{
	if (isFather(vNodeA, vNodeB))
	{
		vAncestor = vNodeA;
		return true;
	}

	if (isFather(vNodeB, vNodeA))
	{
		vAncestor = vNodeB;
		return true;
	}

	TreeNode* Parent = vNodeA->parent;
	while (true)
	{
		if (isFather(Parent, vNodeB))
		{
			vAncestor = Parent;
			return true;
		}
		Parent = Parent->parent;
	}
	return false;
}




019写程序在一棵二叉树中找到两个结点的最近共同祖先（keep it up)






























        

            
                
                  
                
                

                    联系

                    我们