|
题目：二叉树的结点定义如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点
思路：求取2个节点的公共节点，如果2个节点分别在左右子树上，则其根节点为公共节点，如果2个节点都在左子树或者右子树上，则在左子树或者右子树上求取公共最低节点
#include <iostream>
#include <assert.h>
using namespace std;
struct treenode
{
int t_value;
treenode *t_left;
treenode *t_right;
};
void maketree(treenode *&ptr,int value)
{
if (ptr==nullptr)
{
treenode *currentnode=new treenode();
currentnode->t_value=value;
currentnode->t_left=nullptr;
currentnode->t_right=nullptr;
ptr=currentnode;
}
else
{
if (value>ptr->t_value)
{
maketree(ptr->t_right,value);
}
else
{
maketree(ptr->t_left,value);
}
}
}
//在树中搜索cnode，得出cnode属于左树还是右树
bool findnode(const treenode *head,const treenode *cnode)
{
assert(head!=nullptr&&cnode!=nullptr);
if (head==cnode)
{
return true;
}
bool havenode=false;
if (head->t_left!=nullptr)
{
havenode=findnode(head->t_left,cnode);
}
if (havenode==false&&head->t_right!=nullptr)
{
havenode=findnode(head->t_right,cnode);
}
return havenode;
}
//查找公共最低节点
treenode *findbostnode(treenode *head,const treenode *firstnode,const treenode *secondnode)
{
assert(head!=nullptr&&firstnode!=nullptr&&secondnode!=nullptr);
bool leftnode1=false;
bool leftnode2=false;
if (head->t_left!=nullptr)
{
leftnode1=findnode(head->t_left,firstnode);
leftnode2=findnode(head->t_left,secondnode);
}
if (leftnode1&&leftnode2)
{
if (head->t_left==firstnode||head->t_left==secondnode)
{
return head;
}
return findbostnode(head->t_left,firstnode,secondnode);
}
bool rightnode1=false;
bool rightnode2=false;
if (head->t_left!=nullptr)
{
if (!leftnode1)
{
rightnode1=findnode(head->t_right,firstnode);
}
if (!leftnode2)
{
rightnode2=findnode(head->t_right,secondnode);
}
}
if (rightnode1&&rightnode2)
{
if (head->t_right==firstnode||head->t_right==secondnode)
{
return head;
}
return findbostnode(head->t_right,firstnode,secondnode);
}
if ((leftnode1&&rightnode2)||(leftnode2&&rightnode1))
{
return head;
}
}
int main()
{
treenode *ptr=nullptr;
maketree(ptr,12);
maketree(ptr,6);
maketree(ptr,3);
maketree(ptr,2);
maketree(ptr,4);
maketree(ptr,8);
maketree(ptr,7);
treenode *firstnode=ptr->t_left->t_left->t_left;
treenode *secondnode=ptr->t_left->t_right->t_left;
treenode *resultnode=nullptr;
resultnode=findbostnode(ptr,firstnode,secondnode);
cout<<resultnode->t_value<<endl;
return 0;
}
| 
转播
