二叉树两个结点的最低共同父结点 微信：318175542
来源：程序员人生 发布时间：2015-05-15 08:29:28 阅读次数：2763次
入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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
