1143 Lowest Common Ancestor (30 分) BST 公共祖先

ゝ一世哀愁。 2021-10-29 16:52 207阅读 0赞

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 (≤ 1,000), the number of pairs of nodes to be tested; and N (≤10,000), 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.

**题意：**6个询问，8个结点，先序遍历的BST，问x和y的关系

**思路：**先判x和y是否存在，若都存在，再做LCA

经历了多个版本的洗礼，直到我看到了柳神的30行代码，男默女泪。

1.柳神的。将当前结点标记为a，如果u和v分别在a的左、右，或者u、v其中一个就是当前a，

即(a >= u && a <= v) || (a >= v && a <= u)，说明找到了这个共同最低祖先a，退出当前循环。

#include <iostream>
    #include <vector>
    #include <map>
    using namespace std;
    int main() 
    {
        int m,n,u,v,a,i,j;
        scanf("%d %d",&m,&n);
        vector<int> pre(n);
    	map<int, bool> mp;
        for (i=0;i<n;i++) 
    	{
            scanf("%d",&pre[i]);
            mp[pre[i]]=true;
        }
        for(i=0;i<m;i++) 
    	{
            scanf("%d%d",&u,&v);
            for(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;
    }

2.建树，用函数计算——22分，测试点3和4超时

Node* lowestCommonAncestor(Node* root,int p,int q) 
    {
            if(!root)return NULL;
            else if((root->val > p&&root->val < q)||(root->val < p&&root->val > q))
    		return root;
            else if(root->val==p||root->val==q)
    		return root;
            else if(root->val > p&&root->val > q)
    		return lowestCommonAncestor(root->l,p,q);
            else
            return lowestCommonAncestor(root->r,p,q);
    }

3.建树，暴力深搜记录从root到指定结点的路径，对比两条路径。——22分，测试点3和4超时

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    vector<int> pu,pv;
    struct Node
    {
    	int val;
    	struct Node *l,*r;
    	Node()
    	{
    		val=-INF;
    		l=r=NULL;
    	}
    };
    void insert(struct Node* root,int x)
    {
    	if(root->val==-INF)
    	{
    		root->val=x;
    		return;
    	}
        if(x<=root->val)
        {
        	if(root->l==NULL)root->l=new Node;
        	insert(root->l,x);
        }
        else
        {
        	if(root->r==NULL)root->r=new Node;
        	insert(root->r,x);
        }
    }
    void dfs1(Node *root,int o)
    {
    	if(o==root->val) return;
    	else if(o<root->val)
    	{
    		pu.push_back(root->val);
    		dfs1(root->l,o);		
    	}
    	else if(o>root->val)
    	{
    		pu.push_back(root->val);
    		dfs1(root->r,o);
    	}
    }
    void dfs2(Node *root,int o)
    {
    	if(o==root->val) return;
    	else if(o<root->val)
    	{
    		pv.push_back(root->val);
    		dfs2(root->l,o);		
    	}
    	else if(o>root->val)
    	{
    		pv.push_back(root->val);
    		dfs2(root->r,o);
    	}
    }
    int main()
    {
    	int n,m,k,x,y,i,j;
    	map<int,int> ma;
    	Node *root=new Node;
    	scanf("%d%d",&n,&m);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d",&k);
    		ma[k]=1;
    		insert(root,k);
    	}
    	while(n--)
    	{
    		pu.clear();
    		pv.clear();
    		scanf("%d%d",&x,&y);
    		if(ma[x]==0&&ma[y]==0)
    		printf("ERROR: %d and %d are not found.\n",x,y);
    		else if(ma[x]==0)
    		printf("ERROR: %d is not found.\n",x);
    		else if(ma[y]==0)
    		printf("ERROR: %d is not found.\n",y);
    		else
    		{
    			if(x==y)
    			printf("%d is an ancestor of %d.\n",x,y);
    			else
    			{
    				dfs1(root,x);
    				dfs2(root,y);
    				int flag=0;
    				for(i=0;i<pu.size();i++)
    				{
    					if(pu[i]==y)
    					{
    						flag=1;
    						break;
    					}
    				}
    				for(i=0;i<pv.size();i++)
    				{
    					if(pv[i]==x)
    					{
    						flag=2;
    						break;
    					}
    				}
    				if(flag==1)
    				printf("%d is an ancestor of %d.\n",y,x);
    				else if(flag==2)
    				printf("%d is an ancestor of %d.\n",x,y);
    				else
    				{
    					int minn=min(pu.size(),pv.size());
    					for(i=minn-1;i>=0;i--)
    					{
    						if(pu[i]==pv[i])
    						{
    							printf("LCA of %d and %d is %d.\n",x,y,pv[i]);
    							break;
    						}
    					}
    				}			 
    			}		
    		}
    	}
    }

4.屁桃的。不建树，存在数组里。把深度深的结点往上提，知道两个节点在同一层然后一起向上。

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N=10005;
    int a[N],l[N],r[N],fa[N],dep[N];
    int tot=1,root=1;
    bool vis[N];
    void insert(int u,int x)
    {
    	if(!vis[u])
    	{
    		vis[u]=1;
    		a[u]=x;
    		return;
    	}
    	if(x<=a[u])insert(l[u]==0?l[u]=++tot:l[u],x);
    	else insert(r[u]==0?r[u]=++tot:r[u],x);
    }
    map<int,int>hash_map;
    void dfs(int u,int father,int level)
    {
    	fa[u]=father;
    	dep[u]=level;
    	hash_map[a[u]]=u;
    	if(l[u])dfs(l[u],u,level+1);
    	if(r[u])dfs(r[u],u,level+1);
    }
    int lca(int x,int y)
    {
    	if(dep[x]<dep[y])swap(x,y);
    	while(dep[x]!=dep[y])x=fa[x];
    	while(x!=y)x=fa[x],y=fa[y];
    	return x;
    }
    int main()
    {
    	int n,m;
    	scanf("%d%d",&m,&n);
    	for(int i=0;i<n;i++)
    	{
    		int x;
    		scanf("%d",&x);
    		insert(root,x);
    	}
    	dfs(root,-1,0);
    	while(m--)
    	{
    		int u,v;
    		scanf("%d%d",&u,&v);
    		if(hash_map[u]==0&&hash_map[v]==0)
    		printf("ERROR: %d and %d are not found.\n",u,v);
    		else if(hash_map[u]==0)
    		printf("ERROR: %d is not found.\n",u);
    		else if(hash_map[v]==0)
    		printf("ERROR: %d is not found.\n",v);
    		else
    		{
    			int lca_pos=lca(hash_map[u],hash_map[v]);
    			if(lca_pos==hash_map[u])
    			printf("%d is an ancestor of %d.\n",u,v);
    			else if(lca_pos==hash_map[v])
    			printf("%d is an ancestor of %d.\n",v,u);
    			else 
    			printf("LCA of %d and %d is %d.\n",u,v,a[lca_pos]);
    		}
    	}
    	return 0;
    }