⭐⭐⭐⭐⭐PAT A1143 Lowest Common Ancestor

题目描述

知识点

BST的遍历

实现

码前思考

1. 题中指明了给的整数是distinct的；
2. 对于树中的每一个整数，我们使用unordered_set进行保存，从而可以直接判断是否存在于树中，否则查找会花费很大的时间复杂度；
3. 我在第一次写的时候，测试点3，4超时，死活没有找出来原因，后来百度，发现原来是因为我建树的过程是一个一个 insert() 进行的，这种建树方法称为 在线建树 ，而如果直接使用前序序列一次性进行建树，则成为 离线建树 ，由于在线建树每次都会有大量的重复的查找操作，因此时间复杂度非常高，最坏为$O(N^2)$O(N2)！而离线建树的时间复杂度为$O(N)$O(N)，因此，以后还是使用离线建树比较好！
4. 对于如何找到u和v的LCA，只需要从根结点开始寻找，如果出现了两个u和v被分配到不同的子树上，那么当前结点就是LCA。看代码更加直接。

代码实现

//运行超时了 
//建树的一个要点，直接进行建树会多很多查找的时间复杂度!!!! 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1e4+10;

struct node{
	int val;
	node* l;
	node* r;
	node(int v):val(v),l(NULL),r(NULL){}
};

int m;
int n;
int data[maxn];
unordered_set<int> st; 

node* create(int preL,int preR){
	
	if(preL > preR){
		return NULL;
	}else{
		node* root = new node(data[preL]);
		int numLeft=0;
		for(int i=preL+1;i<=preR;i++){
			if(data[i] < root->val){
				numLeft++;
			}else{
				break;
			}
		}
		
		root->l = create(preL+1,preL+numLeft);
		root->r = create(preL+numLeft+1,preR);
		return root;
	}
} 

//共同点一定出现在某个分叉处 
void find(node* root,int u,int v,int& lca){
	if(root->val > u && root->val > v){
		find(root->l,u,v,lca);
	}else if(root->val < u && root->val < v){
		find(root->r,u,v,lca);
	}else{
		lca = root->val;
	}
	return; 
}


int main(){
	scanf("%d %d",&m,&n);

	
	for(int i=0;i<n;i++){
		scanf("%d",&data[i]);		
		st.insert(data[i]); 
	}
	
	node* root = NULL;
	root = create(0,n-1);
	
	//开始进行判断
	for(int i=0;i<m;i++){
		int u;
		int v;
		scanf("%d %d",&u,&v);
		if(st.find(u) == st.end() && st.find(v) == st.end()){
			printf("ERROR: %d and %d are not found.\n",u,v);
		}else if(st.find(u) == st.end() && st.find(v) != st.end()){
			printf("ERROR: %d is not found.\n",u);
		}else if(st.find(u) != st.end() && st.find(v) == st.end()){
			printf("ERROR: %d is not found.\n",v);
		}else{
			int lca;
			find(root,u,v,lca);
			if(lca == u){
				printf("%d is an ancestor of %d.\n",u,v);
			}else if(lca == v){
				printf("%d is an ancestor of %d.\n",v,u);
			}else{
				printf("LCA of %d and %d is %d.\n",u,v,lca);
			}			
		} 
		
	} 
	
	return 0;
}

码后反思

1. 我之前还窃喜可以直接用先序遍历直接构建BST，结果这就栽了一个跟头，以后还是采用离线的方式算了；
2. 柳神是直接利用了前序遍历序列的性质，都不用建树，实在是牛逼，佩服佩服。

   #include <iostream>
   #include <vector>
   #include <map>
   using namespace std;
   map<int, bool> mp;
   int main() {
       int m, n, u, v, a;
       scanf("%d %d", &m, &n);
       vector<int> pre(n);
       for (int i = 0; i < n; i++) {
           scanf("%d", &pre[i]);
           mp[pre[i]] = true;
       }
       for (int i = 0; i < m; i++) {
           scanf("%d %d", &u, &v);
           for(int j = 0; j < n; j++) {
               a = pre[j];
               if ((a >= u && a <= v) || (a >= v && a <= u)) break;
           } 
           if (mp[u] == false && mp[v] == false)
               printf("ERROR: %d and %d are not found.\n", u, v);
           else if (mp[u] == false || mp[v] == false)
               printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);
           else if (a == u || a == v)
               printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
           else
               printf("LCA of %d and %d is %d.\n", u, v, a);
       }
       return 0;
   }