总结

• 显然本题的考点是怎么找出这个最小公共祖先
• 文章来源：LawsonAbs@CSDN
• 相关例题：【LeetCode】二叉树的最近公共祖先
• PAT本题的代码尚未AC

1.题意

给出中序和先序遍历序列，让你找出给定的查询记录的最小父节点，如果给定的值不存在，则按照相应的格式输出。指定的格式如下：

For each given pair of U and V, print in a line LCA of U and V is A. if the LCA is found and A is the key. But if A is one of U and V, print X is an ancestor of Y. where X is A and Y is the other node. If U or V is not found in the binary tree, print in a line ERROR: U is not found. or ERROR: V is not found. or ERROR: U and V are not found…

2.分析

主要实现步骤如下：

• step 1:根据先序和中序建树
• step 2:根据建好的数，找到每个节点的父节点，并放入到vector中
• step 3:找出两个给定值的所有父节点信息，然后使用双层for循环找出其最小的公共父节点。

问题是：代码超时。

3.代码

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

int in[maxn];
int pre[maxn];
set<int> tree;//保存二叉树的值 
int N,M;
vector<int> sun[maxn];//保存儿子节点的值 


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


node* create(int preL,int preR,int inL,int inR){
	if(preL > preR){
		return NULL;
	}
	node* root = new node;
	root->data = pre[preL];//将pre的preL值放入到结构体中
	int i ;
	for(i = inL; i <= inR;i++) {
		if(in[i] == pre[preL]) break;
	}
	int numLeft = i - inL;//看左边是否还有节点 
	//注意这里没有对numLeft的数目进行判断！！ 
	root->lchild = create(preL+1,preL+numLeft,inL,i-1);
	root->rchild = create(preL+numLeft+1,preR,i+1,inR);	
	return root;
}

//inOrder
void inOrder(node* root){
	if(root->lchild != NULL ) inOrder(root->lchild);
	cout << root->data << " ";	
	if(root->rchild != NULL ) inOrder(root->rchild);	
}

//存每个节点的父节点 
void trav(node* root) {
	if(root->lchild != NULL) {//如果左子树不为空 
		sun[root->lchild->data].push_back(root->data);		
		trav(root->lchild); 
	}
	tree.insert(root->data);//放入到set中
	if(root->rchild != NULL) {
		sun[root->rchild->data].push_back(root->data);
		trav(root->rchild);
	}
}

bool find(int value){
	if(tree.find(value)!=tree.end()) return true;
	return false;
}
int main(){
	cin >> M >> N;
	int i,j;
	for(i = 0;i< N;i++) cin >> in[i];
	for(i = 0;i< N;i++) cin >> pre[i];
	node* root;
	root = create(0,N-1,0,N-1);
	trav(root);
	
	int root_val = root->data;//表示根节点的值 	
	int que1,que2;
	while(M){
		cin >> que1 >> que2;
		int index1 = 0,index2 = 0;
		int flag = 0;
		int fa1[maxn],fa2[maxn]; //que1的父节点 que2的父节点 
		if( find(que1) && find(que2) ) {//说明找到了值 ，进行查询  
			fa1[index1++] = que1;
			fa2[index2++] = que2;//将自身加入到父节点中 
			while(fa1[index1-1] != root_val) {//如果没有到根节点，则继续进行 				
				fa1[index1] = sun[fa1[index1-1]].front();				
				index1++;
			}
			while(fa2[index2-1] != root_val) {
				fa2[index2] = sun[fa2[index2-1]].front(); 				
				index2++;
			}
			for(i = 0;i< index1;i++){
				for(j = 0;j< index2;j++){
					if( fa2[j] == fa1[i]){
						flag = 1;//说明找到公共父节点了 
						break;
					}
				}
				if(flag == 1)	break;				
			}		
			
			if(que1 != fa1[i] && que2!=fa1[i] ) 
				cout <<"LCA of "<< que1<<" and "<< que2 <<" is "<< fa1[i]<<".\n";
			else if(que1 == fa1[i]) cout << que1 <<" is an ancestor of " <<que2<<".\n";
			else if(que2 == fa1[i]) cout << que2 <<" 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--;
	}
}

很明显，就是因为双层for循环导致了运行超时。现在的问题就是如何快速找到这个最小祖先。

4.测试用例

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


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

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

超时的样例是最后两个测试用例，如下图所示：

我尝试不在while(M–)循环中重复生成que1,que2的祖宗序列，而是有则直接使用，无则继续生成。然后将其中部分代码改成如下的样子：

	int que1,que2;//待查询的两个值 
	while(M){
		cin >> que1 >> que2;		
		int flag = 0;		
		if( find(que1) && find(que2) ) {//说明找到了值 ，进行查询 
			if(fa[que1].size()==0){				
				fa[que1].push_back(que1);//将自身加入到父节点中 
				while(fa[que1].back() != root_val) {//如果没有到根节点，则继续进行 				
					fa[que1].push_back(sun[fa[que1].back()].front());					
				}	
			} 
			
			if(fa[que2].size()==0){				
				fa[que2].push_back(que2);//将自身加入到父节点中 
				while(fa[que2].back() != root_val) {//如果没有到根节点，则继续进行 
					fa[que2].push_back(sun[fa[que2].back()].front());					
				}	
			} 	
			for(i = 0;i< fa[que1].size();i++){
				for(j = 0;j< fa[que2].size();j++){
					if( fa[que2][j] == fa[que1][i]){
						flag = 1;//说明找到公共父节点了 
						break;
					}
				}
				if(flag == 1)	break;				
			}		
			
			if(que1 != fa[que2][j] && que2 != fa[que2][j] ) 
				cout <<"LCA of "<< que1<<" and "<< que2 <<" is "<< fa[que2][j]<<".\n";
			else if(que1 == fa[que2][j]) cout << que1 <<" is an ancestor of " <<que2<<".\n";
			else if(que2 == fa[que2][j]) cout << que2 <<" 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--;
	}

这样的确能够避免重复生成某个节点的祖宗序列，但是会耗用巨大的内存空间（否则会引起段错误，因为每个节点的值的范围是int型），然后报 “内存超限” 的错误。