[数据结构与算法]PTA 二叉搜索树的最近公共祖先

题目

.给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。

输入

输入的第一行给出两个正整数：待查询的结点对数 M（≤ 1 000）和二叉搜索树中结点个数 N（≤ 10 000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M 行，每行给出一对整数键值 U 和 V。所有键值都在整型int范围内。

输出

对每一对给定的 U 和 V，如果找到 A 是它们的最近公共祖先结点的键值，则在一行中输出 LCA of U and V is A.。但如果 U 和 V 中的一个结点是另一个结点的祖先，则在一行中输出 X is an ancestor of Y.，其中 X 是那个祖先结点的键值，Y 是另一个键值。如果 二叉搜索树中找不到以 U 或 V 为键值的结点，则输出 ERROR: U is not found. 或者 ERROR: V is not found.，或者 ERROR: U and V are not found.。

输入样例

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

输出样例

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

题目分析

经分析，二叉搜索树的中序遍历结果便是所有键值的升序排列，题目给出了先序遍历结果，那么我们可以以此来构建二叉搜索树。原理可戳这里。
在建树时，因为便于内存管理，此处并没有按照直接在堆区域通过new开辟空间的方法,采用了结构体数组的方式，构造逻辑上的链表，通过指针来实现父子结点之间的关系。具体可见代码。
在实现是否父子结点的判定时，通过分析两数值与根节点的关系，若一大一小，则该根节点为共同的祖先结点，若是相同，则向下判定其子树的根节点与二者的大小关系。

代码

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
typedef struct Node* Tree;
struct Node{
	int key;
	Tree left = 0,right = 0;
}tree[10005];
int n,cnt,a[10005],b[10005];
map<int,int> mp;

Tree creat(int len,int loc,int start){
	if(len < 1) return 0;
	Tree T = &tree[cnt++];//保存地址该子树根节点的地址
	T->key = a[loc];
	int m = 0;
	m = lower_bound(b+m+start,b+len+start,a[loc])-b-start;//寻找树的根节点的位置
	T->left = creat(m,loc+1,start);//在范围内递归建树
	T->right= creat(len-m-1,loc+m+1,start+m+1);
	return T;//返回地址，由父结点指向左右子结点
}

int find(int x,int y,Tree Tr){//查找祖先结点
	if(x>Tr->key&&y>Tr->key)//大小比较结果情况相同
		return find(x,y,Tr->right);
	else if(x<Tr->key&&y<Tr->key)//情况不同
		return find(x,y,Tr->left);
	else return Tr->key;//如果有数值与该根节点相同时，返回该值
}

int main(){
	Tree T;
	int m;
	cin >> m >> n;
	for(int i = 0;i<n;++i){
		scanf("%d",&b[i]);
		a[i]=b[i];
		mp[a[i]] = 1;//标记该数值存在
	}
	sort(b,b+n);//获得中序遍历结果
	T = creat(n,0,0);//建树
	int u,v,k;
	while(m--){
		scanf("%d %d",&u,&v);
		//查找两个数值是否在树中均存在
		if(mp[u]==0&&mp[v]==0) cout <<"ERROR: "<<u<<" and "<<v<<" are not found."<<endl;
		else if(mp[u]==0) cout <<"ERROR: "<<u<<" is not found."<<endl;
		else if(mp[v]==0) cout <<"ERROR: "<<v<<" is not found."<<endl;
		else{//都存在时，判定
			k = find(u,v,T);//查找最近的祖先结点值
			if(k == u) cout <<u<<" is an ancestor of "<<v<<"."<<endl;
			else if(k == v) cout <<v<<" is an ancestor of "<<u<<"."<<endl;
			else cout <<"LCA of "<<u<<" and "<<v<<" is "<<k<<"."<<endl;
		}
	}
	return 0;
}

运行结果