版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 题目 查找二叉树的最近公共祖先 示例如下: 节点6和节点8的最近公共祖先是节点4 节点2和节点5的最近公共祖先也是节点0 节点4和节点7的最近公共祖先也是节点4 思路 1）采用中序遍历(先左子树-> 根 -> 右子树) 可以得到每个节点在树中的层级 2）扫描2个目标节点之间所有节点，层级最小的节点，即为最近公共祖先
ancestor.cpp
#include <iostream> #include <stack> #include <vector> using namespace std; #define MAX_VALUE 1000000 struct node{ int data; struct node* lchild; struct node* rchild; }; typedef struct node Node; int levels[100]; int lca(Node* root,int m,int n){ Node* p = root; vector<int> v; stack<Node*> s; int level = 0; cout<<"中序遍历:"<<endl; while(p||!s.empty()){ if(p){ s.push(p); levels[p->data]=level; p = p->lchild; level++; }else{ p = s.top(); level = levels[p->data]; s.pop(); cout<<p->data<<" "; v.push_back(p->data); p = p->rchild; level++; } } cout<<endl; cout<<"节点对应层级:"<<endl; for(int i=0;i<v.size();i++){ cout<<levels[v[i]]<<" "; } cout<<endl; int minLevel = MAX_VALUE; int res = -1; bool flag = false; for(int i=0;i<v.size();i++){ if(v[i]==m||v[i]==n){ if(levels[v[i]]<minLevel){ res = v[i]; minLevel = levels[v[i]]; } flag = !flag; }else if(flag){ if(levels[v[i]]<minLevel){ res = v[i]; minLevel = levels[v[i]]; } } } return res; } int main(){ Node node0={0,NULL,NULL}; Node node1={1,NULL,NULL}; Node node4={4,NULL,NULL}; Node node2={2,NULL,NULL}; Node node3={3,NULL,NULL}; Node node5={5,NULL,NULL}; Node node6={6,NULL,NULL}; Node node7={7,NULL,NULL}; Node node8={8,NULL,NULL}; node0.lchild = &node1; node0.rchild = &node4; node1.lchild = &node2; node1.rchild = &node3; node4.lchild = &node5; node4.rchild = &node8; node5.lchild = &node6; node5.rchild = &node7; int n = 0; n = lca(&node0,6,8); cout<<"节点6和节点8的最近公共祖先是"<<n<<endl; n = lca(&node0,2,5); cout<<"节点2和节点5的最近公共祖先是"<<n<<endl; n = lca(&node0,4,7); cout<<"节点4和节点7的最近公共祖先是"<<n<<endl; } 输出 中序遍历: 2 1 3 0 6 5 7 4 8 节点对应层级: 2 1 2 0 3 2 3 1 2 节点6和节点8的最近公共祖先是4 中序遍历: 2 1 3 0 6 5 7 4 8 节点对应层级: 2 1 2 0 3 2 3 1 2 节点2和节点5的最近公共祖先是0 中序遍历: 2 1 3 0 6 5 7 4 8 节点对应层级: 2 1 2 0 3 2 3 1 2 节点4和节点7的最近公共祖先是4 PS 2012年写的练习小程序
...