【1143】Lowest Common Ancestor (30分)

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      map<int,bool> mp;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      PS:map<int,bool> mp用来标记出现的结点，遍历 一遍pre数组~vector，如果pre[i]满足BST的要求(if内)则break
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	int m,n,u,v,a;
     
    
   

    

     

    
    

     
	scanf("%d %d",&m,&n);//m次查询，n个结点
     
    
   

    

     

    
    

     
	vector<int> pre(n);
     
    
   

    

     

    
    

     
	for(int i=0;i<n;i++){
     
    
   

    

     

    
    

     
		scanf("%d",&pre[i]);//vector存入二叉搜索树的前序遍历序列
     
    
   

    

     

    
    

     

      		mp[pre[i]]=true;//标记树中所有出现过的结点
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(int i=0;i<m;i++){//m次查询
     
    
   

    

     

    
    

     
		scanf("%d %d",&u,&v);//查询u和v的LCA
     
    
   

    

     

    
    

     
		for(int j=0;j<n;j++){//n个结点
     
    
   

    

     

    
    

     

      			a=pre[j];
     
    
   

    

     

    
    

     
			if((a>=u && a<=v)||(a>=v && a<=u)) break;
     
    
   

    

     

    
    

     
			//BST:每个节点的值大于(小于)其！！任意！！左侧子节点的值，
     
    
   

    

     

    
    

     
			//小于(大于)其任意右节点的值，这个a是唯一的！(如果存在的话)
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		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);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/103797094