二叉树两个结点的最低共同父结点 微信:318175542

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

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

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

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

另外一种实现:

/*
求2叉树中两个节点的最低公共先人节点
*/

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

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 二叉树两个结点的最低共同父结点 微信:318175542

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡