PAT 1143 Lowest Common Ancestor 【C++版】

PAT 1143 Lowest Common Ancestor 【C++版】

1.题意

给出一个二叉搜索树的先序序列，让你求出其两个节点的最小公共父节点。

2.分析

这个很好实现，步骤如下：

• step 1:根据先序序列和中序序列（BST的中序序列就是从小到大，或者从大到小的排列）构建一棵二叉树
• step 2:根据给出的两个值找到节点的公共节点。是最小的公共节点必须满足的特点是：该节点的值大于等于a，并且小于等于b；或者是该节点的值大于等于b，并且小于等于a。【递归的边界返回条件】
• step 3:如果不满足2，则递归相应的左子树或者到右子树再次判断，直至满足。

3.代码

#include<cstdio> 
#include<vector>
#include<iostream>
#include<algorithm>
#include<set>
#define maxn 10005
using namespace std;

int N,M;
int pre[maxn];//先序遍历 
int in[maxn];//中序遍历 
set<int> tree;//树中所有值的集合

struct node{
	node* lchild;
	node* rchild;
	int data;
}; 

node* create(int preL,int preR,int inL,int inR){
	if(preL > preR) return NULL;
	node* root = new node;
	root->data = pre[preL];
	
	int  i;
	for(i = inL;i< inR;i++){
		if(in[i] == pre[preL]) break;//跳出 
	}
	int numLeft = i-inL;	
	root->lchild = create(preL+1,preL+numLeft,inL,i-1) ;
	root->rchild = create(preL+numLeft+1,preR,i+1,inR);
	return root;
}

void inOrder(node* root){
	if(root->lchild!=NULL) inOrder(root->lchild);//遍历左子树 
	tree.insert(root->data) ;//insert into set
	if(root->rchild!=NULL) inOrder(root->rchild);//遍历右子树 
} 

//找值 
bool find (int val){
	if(tree.find(val)!=tree.end()) return true;
	return false;
}

//找节点a,节点b的最小祖宗 
int findMinFat(node* root,int a,int b) {		
	if((root->data >= a && root->data <= b) 
	|| (root->data <= a && root->data >= b)){//循环终止条件 
		return root->data;	 
	}	
	else if(root->data > a && root->data > b) {
		findMinFat(root->lchild,a,b);//进入到左子树 
	}
	else if(root->data < a && root->data < b){
		findMinFat(root->rchild,a,b);//进入到右子树 
	}
}

int main(){
	cin >> M>>N ;
	int i,j;
	
	for(i = 0;i< N;i++){
		cin >> pre[i];
		in[i] = pre[i];
	}
	sort(in,in+N);//排序得到中序输出 
	node* root = create(0,N-1,0,N-1);
	inOrder(root);
	int que1,que2;
	while(M){
		cin >> que1 >> que2;		
		int flag = 0;		
		int ance;
		if( find(que1) && find(que2) ) {//说明找到了值 ，进行查询 
			ance = findMinFat(root,que1,que2);//找这两个根的最小祖宗 
			if(que1 != ance && que2!=ance ) 
				cout <<"LCA of "<< que1<<" and "<< que2 <<" is "<< ance<<".\n";
			else if(que1 == ance) cout << ance <<" is an ancestor of " <<que2<<".\n";
			else if(que2 == ance) cout << ance <<" is an ancestor of " <<que1<<".\n";
		}
		else{
			if(!find(que1) && !find(que2)){
				cout << "ERROR: "<< que1<<" and "<<que2<<" are not found.\n";
			}
			else if(!find(que1) && find(que2)){
				cout << "ERROR: "<< que1<<" is not found.\n";
			}
			else if(find(que1) && !find(que2)){
				cout << "ERROR: "<< que2<<" is not found.\n";
			}
		} 
		M--;
	}
} 

4.测试用例

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


2 8
6 3 1 2 5 4 8 7
8 3
5 1

注意我给出的第二个测试用例，其特性都是给出的值 a > b。

5.执行结果