题目:二叉树的结点定义如下:
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; }