二叉树两个结点的最低共同父结点 微信：318175542
发布时间：2020-12-13 20:10:10 所属栏目：PHP教程 来源：网络整理
导读：入2叉树中的两个结点，输出这两个结点在数中最低的共同父结点。 分析：求数中两个结点的最低共同结点是面试中常常出现的1个问题。这个问题至 少有两个变种。 第1变种是2叉树是1种特殊的2叉树：查找2叉树。也就是树是排序过的，位于 左子树上的结点都比父结点
|
入2叉树中的两个结点，输出这两个结点在数中最低的共同父结点。 分析：求数中两个结点的最低共同结点是面试中常常出现的1个问题。这个问题至 少有两个变种。 第1变种是2叉树是1种特殊的2叉树：查找2叉树。也就是树是排序过的，位于 左子树上的结点都比父结点小， 而位于右子树的结点都比父结点大。 我们只需要从根结点开 始和两个结点进行比较。 如果当前结点的值比两个结点都大， 则最低的共同父结点1定在当 前结点的左子树中。 如果当前结点的值比两个结点都小， 则最低的共同父结点1定在当前结 点的右子树中。 第2个变种是树不1定是2叉树，每一个结点都有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,second);
else
return root;
}
}
另外一种实现： /*
求2叉树中两个节点的最低公共先人节点
*/
BinTree* LCA(BinTree* root,BinTree* second)
{
if(root == first || root == second )
return root;
if(root == NULL)
return NULL;
BinTree* left = LCA(root->left,second);
BinTree* right = LCA(root->right,second);
if(left == NULL)
return right;
else if(right == NULL)
return left;
else
return root;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |