PAT甲级1143. Lowest Common Ancestor （BST共同祖先）

傷城~ 2022-05-29 07:13 139阅读 0赞

# 1143. Lowest Common Ancestor (30) #

时间限制

200 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.

A binary search tree (BST) is recursively defined as a binary tree which has the following properties:

*  The left subtree of a node contains only nodes with keys less than the node's key.
 *  The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
 *  Both the left and right subtrees must also be binary search trees.

Given any two nodes in a BST, you are supposed to find their LCA.

**Input Specification:**

Each input file contains one test case. For each case, the first line gives two positive integers: M (<= 1000), the number of pairs of nodes to be tested; and N (<= 10000), the number of keys in the BST, respectively. In the second line, N distinct integers are given as the preorder traversal sequence of the BST. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of **int**.

**Output Specification:**

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 BST, print in a line "ERROR: U is not found." or "ERROR: V is not found." or "ERROR: U and V are not found.".

**Sample Input:**

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

**Sample Output:**

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.

自己用链表写，递归查找3， 4样例过不了， 于是在网上借鉴别人通过数组模拟BST，但是自己建树方式跟他不一样，我传参用了引用，感觉时间上应该是一样的， 但是不知道为什么我的三四样例会T， 求大神指教。

代码一：我自己建树方式：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<map>
    #include<set>
    using namespace std;
    const int maxn=220;
    int m, n;
    
    map<int, int> s;
    struct node{
      int x;
      int l, r;
    }tree[1000000];
    
    void insert(int& root, int id){//就是这个地方，感觉不会耗时啊！！
      if(root==-1){
        root=id;
        return;
      }
      if(tree[id].x>=tree[root].x)
        insert(tree[root].r, id);
      else
        insert(tree[root].l, id);
    }
    
    
    
    int main(){
      int root=-1;
      scanf("%d%d", &m, &n);
      
      for(int i=1; i<=n; i++)
      {
        int tmp;
        scanf("%d", &tree[i].x);
        s[tree[i].x]=1;
        tree[i].l=tree[i].r=-1;
        insert(root, i);
      } 
      
      while(m--){
        int x, y;
        scanf("%d%d", &x, &y);
        
        if(s[x] && !s[y])
          printf("ERROR: %d is not found.\n", y);
        else if(!s[x] && s[y])
          printf("ERROR: %d is not found.\n", x);
        else if(!s[x] && !s[y])
          printf("ERROR: %d and %d are not found.\n", x, y);
        else{
          
          int r=1;
          while(r!=-1){
            if(tree[r].x==x || tree[r].x==y)
              break;
            if(tree[r].x<=x && tree[r].x<=y)
              r=tree[r].r;
            else if(tree[r].x>x && tree[r].x>y)
              r=tree[r].l;
            else
              break;
          }
          if(tree[r].x==x)
            printf("%d is an ancestor of %d.\n", x, y);
          else if(tree[r].x==y)
            printf("%d is an ancestor of %d.\n", y, x);
          else 
            printf("LCA of %d and %d is %d.\n", x, y, tree[r].x);
        }  
        
      }
      
        return 0;
    }

代码二：别人的建树方式：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<map>
    #include<set>
    using namespace std;
    const int maxn=220;
    int m, n;
    
    map<int, int> s;
    struct node{
    	int x;
    	int l, r;
    }tree[1000000];
    
    void insert(int root, int id){//感觉就少了一层递归，难道因为这样就wa了？
    	if(tree[id].x>=tree[root].x)
    		if(tree[root].r==-1)
    			tree[root].r=id;
    		else insert(tree[root].r, id);
    	else
    		if(tree[root].l==-1)
    			tree[root].l=id;
    		else
    			insert(tree[root].l, id);
    }
    
    
    
    int main(){
    	scanf("%d%d", &m, &n);
    	int tmp;
    	scanf("%d", &tmp);
    	tree[1].x=tmp; tree[1].l=tree[1].r=-1; s[tmp]=1;
    	for(int i=2; i<=n; i++)
    	{
    		scanf("%d", &tree[i].x);
    		s[tree[i].x]=1;
    		tree[i].l=tree[i].r=-1;
    		insert(1, i);
    	} 
    	
    	while(m--){
    		int x, y;
    		scanf("%d%d", &x, &y);
    		
    		if(s[x] && !s[y])
    			printf("ERROR: %d is not found.\n", y);
    		else if(!s[x] && s[y])
    			printf("ERROR: %d is not found.\n", x);
    		else if(!s[x] && !s[y])
    			printf("ERROR: %d and %d are not found.\n", x, y);
    		else{
    			
    			int r=1;
    			while(r!=-1){
    				if(tree[r].x==x || tree[r].x==y)
    					break;
    				if(tree[r].x<=x && tree[r].x<=y)
    					r=tree[r].r;
    				else if(tree[r].x>x && tree[r].x>y)
    					r=tree[r].l;
    				else
    					break;
    			}
    			if(tree[r].x==x)
    				printf("%d is an ancestor of %d.\n", x, y);
    			else if(tree[r].x==y)
    				printf("%d is an ancestor of %d.\n", y, x);
    			else 
    				printf("LCA of %d and %d is %d.\n", x, y, tree[r].x);
    		}	
    		
    	}
    	
        return 0;
    }