版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

题目

查找二叉树的最近公共祖先 示例如下: 图示

  1. 节点6和节点8的最近公共祖先是节点4
  2. 节点2和节点5的最近公共祖先也是节点0
  3. 节点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年写的练习小程序

请我喝瓶饮料

微信支付码