C++实现寻找最低公共父节点的方法
本文实例讲述了C++实现寻找最低公共父节点的方法，是数据结构中二叉树的经典算法。分享给大家供大家参考。具体方法如下：
最低公共父节点，意思很好理解。
思路1：最低公共父节点满足这样的条件：两个节点分别位于其左子树和右子树，那么定义两个bool变量，leftFlag和rightFlag，如果在左子树中，leftFlag为true，如果在右子树中，rightFlag为true，仅当leftFlag==rightFlag==true时，才能满足条件。
实现代码如下：
#include<iostream>
usingnamespacestd;
structNode
{
Node(inti=0,Node*pLeft=NULL,Node*pRight=NULL):data(i),left(pLeft),
right(pRight){}
Node*left;
Node*right;
intdata;
};
Node*constructNode(Node**pNode1,Node**pNode2)
{
Node*node12=newNode(12);
Node*node11=newNode(11);
Node*node10=newNode(10);
Node*node9=newNode(9,NULL,node12);
Node*node8=newNode(8,node11,NULL);
Node*node7=newNode(7);
Node*node6=newNode(6);
Node*node5=newNode(5,node8,node9);
Node*node4=newNode(4,node10);
Node*node3=newNode(3,node6,node7);
Node*node2=newNode(2,node4,node5);
Node*node1=newNode(1,node2,node3);
*pNode1=node6;
*pNode2=node12;
returnnode1;
}
boolisNodeIn(Node*root,Node*node1,Node*node2)
{
if(node1==NULL||node2==NULL)
{
throw("invalidnode1andnode2");
returnfalse;
}
if(root==NULL)
returnfalse;
if(root==node1||root==node2)
{
returntrue;
}
else
{
returnisNodeIn(root->left,node1,node2)||isNodeIn(root->right,node1,node2);
}
}
Node*lowestFarther(Node*root,Node*node1,Node*node2)
{
if(root==NULL||node1==NULL||node2==NULL||node1==node2)
{
returnNULL;
}
boolleftFlag=false;
boolrightFlag=false;
leftFlag=isNodeIn(root->left,node1,node2);
rightFlag=isNodeIn(root->right,node1,node2);
if(leftFlag==true&&rightFlag==true)
{
returnroot;
}
elseif(leftFlag==true)
{
returnlowestFarther(root->left,node1,node2);
}
else
{
returnlowestFarther(root->right,node1,node2);
}
}
voidmain()
{
Node*node1=NULL;
Node*node2=NULL;
Node*root=constructNode(&node1,&node2);
cout<<"node1:"<<node1->data<<endl;
cout<<"node2:"<<node2->data<<endl;
cout<<"root:"<<root->data<<endl;
Node*father=lowestFarther(root,node1,node2);
if(father==NULL)
{
cout<<"nocommonfather"<<endl;
}
else
{
cout<<"father:"<<father->data<<endl;
}
}
这类问题在面试的时候常会遇到，对此需要考虑以下情形：
1.node1和node2指向同一节点，这个如何处理
2.node1或node2有不为叶子节点的可能性吗
3.node1或node2一定在树中吗
还要考虑一个效率问题，上述代码中用了两个递归函数，而且存在不必要的递归过程，仔细思考，其实一个递归过程足以解决此问题
实现代码如下：
#include<iostream>
usingnamespacestd;
structNode
{
Node(inti=0,Node*pLeft=NULL,Node*pRight=NULL):data(i),
left(pLeft),right(pRight){}
intdata;
Node*left;
Node*right;
};
Node*constructNode(Node**pNode1,Node**pNode2)
{
Node*node12=newNode(12);
Node*node11=newNode(11);
Node*node10=newNode(10);
Node*node9=newNode(9,NULL,node12);
Node*node8=newNode(8,node11,NULL);
Node*node7=newNode(7);
Node*node6=newNode(6);
Node*node5=newNode(5,node8,node9);
Node*node4=newNode(4,node10);
Node*node3=newNode(3,node6,node7);
Node*node2=newNode(2,node4,node5);
Node*node1=newNode(1,node2,node3);
*pNode1=node6;
*pNode2=node5;
returnnode1;
}
boollowestFather(Node*root,Node*node1,Node*node2,Node*&dest)
{
if(root==NULL||node1==NULL||node2==NULL||node1==node2)
returnfalse;
if(root==node1||root==node2)
returntrue;
boolleftFlag=lowestFather(root->left,node1,node2,dest);
boolrightFlag=lowestFather(root->right,node1,node2,dest);
if(leftFlag==true&&rightFlag==true)
{
dest=root;
}
if(leftFlag==true||rightFlag==true)
returntrue;
}
intmain()
{
Node*node1=NULL;
Node*node2=NULL;
Node*root=constructNode(&node1,&node2);
boolflag1=false;
boolflag2=false;
Node*dest=NULL;
boolflag=lowestFather(root,node1,node2,dest);
if(dest!=NULL)
{
cout<<"lowestcommonfather:"<<dest->data<<endl;
}
else
{
cout<<"nocommonfather!"<<endl;
}
return0;
}
下面再换一种方式的写法如下：
#include<iostream>
usingnamespacestd;
structNode
{
Node(inti=0,Node*pLeft=NULL,Node*pRight=NULL):data(i),
left(pLeft),right(pRight){}
intdata;
Node*left;
Node*right;
};
Node*constructNode(Node**pNode1,Node**pNode2)
{
Node*node12=newNode(12);
Node*node11=newNode(11);
Node*node10=newNode(10);
Node*node9=newNode(9,NULL,node12);
Node*node8=newNode(8,node11,NULL);
Node*node7=newNode(7);
Node*node6=newNode(6);
Node*node5=newNode(5,node8,node9);
Node*node4=newNode(4,node10);
Node*node3=newNode(3,node6,node7);
Node*node2=newNode(2,node4,node5);
Node*node1=newNode(1,node2,node3);
*pNode1=node11;
*pNode2=node12;
returnnode1;
}
Node*lowestFather(Node*root,Node*node1,Node*node2)
{
if(root==NULL||node1==NULL||node2==NULL||node1==node2)
returnNULL;
if(root==node1||root==node2)
returnroot;
Node*leftFlag=lowestFather(root->left,node1,node2);
Node*rightFlag=lowestFather(root->right,node1,node2);
if(leftFlag==NULL)
returnrightFlag;
elseif(rightFlag==NULL)
returnleftFlag;
else
returnroot;
}
intmain()
{
Node*node1=NULL;
Node*node2=NULL;
Node*root=constructNode(&node1,&node2);
boolflag1=false;
boolflag2=false;
Node*dest=NULL;
Node*flag=lowestFather(root,node1,node2);
if(flag!=NULL)
{
cout<<"lowestcommonfather:"<<flag->data<<endl;
}
else
{
cout<<"nocommonfather!"<<endl;
}
return0;
}
希望本文所述对大家C++程序算法设计的学习有所帮助。