二叉搜索树的最近公共祖先

雨点打透心脏的1/2处 2022-03-06 13:26 254阅读 0赞

### 题目： ###

7-15 二叉搜索树的最近公共祖先 （30 分)

给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。

### 输入格式： ###

输入的第一行给出两个正整数：待查询的结点对数 M（≤ 1 000）和二叉搜索树中结点个数 N（≤ 10 000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M 行，每行给出一对整数键值 U 和 V。所有键值都在整型**int**范围内。

### 输出格式： ###

对每一对给定的 U 和 V，如果找到 `A` 是它们的最近公共祖先结点的键值，则在一行中输出 `LCA of U and V is A.`。但如果 U 和 V 中的一个结点是另一个结点的祖先，则在一行中输出 `X is an ancestor of Y.`，其中 `X` 是那个祖先结点的键值，`Y` 是另一个键值。如果 二叉搜索树中找不到以 U 或 V 为键值的结点，则输出 `ERROR: U is not found.` 或者 `ERROR: V is not found.`，或者 `ERROR: U and V are not found.`。

### 输入样例： ###

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

### 输出样例： ###

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.

### 分析：根据先序遍历和二叉搜索树的性质建树，再暴力判断就好了。 ###

### 代码： ###

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e4+10;
    int a[N],b[N],vs[N],f[N],ls[N],rs[N],n,m,rt;
    int res,ans;
    
    void ins(int o,int u) {
        if(u<o) {
            if(ls[o]) ins(ls[o],u);
            else {
                ls[o]=u;
                f[u]=o;
            }
        }else {
            if(rs[o]) ins(rs[o],u);
            else {
                rs[o]=u;
                f[u]=o;
            }
        }
    }
    
    void fd(int u) {
        if(!u) return ;
        if(vs[u]) {
            ans=u;
            return ;
        }
        vs[u]=1;
        fd(f[u]);
    }
    
    int main() {
        scanf("%d%d",&m,&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
        sort(b+1,b+1+n);
        for(int i=1;i<=n;i++) {
            a[i]=lower_bound(b+1,b+1+n,a[i])-b;
            if(i==1) rt=a[i];
            else ins(rt,a[i]);
        }
        for(int i=1;i<=m;i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            int uu=lower_bound(b+1,b+1+n,u)-b;
            int vv=lower_bound(b+1,b+1+n,v)-b;
            if(b[uu]!=u&&b[vv]!=v) printf("ERROR: %d and %d are not found.\n",u,v);
            else if(b[uu]!=u) printf("ERROR: %d is not found.\n",u);
            else if(b[vv]!=v) printf("ERROR: %d is not found.\n",v);
            else {
                fd(uu);
                if(vs[vv]) printf("%d is an ancestor of %d.\n",v,u);
                else {
                    fd(vv);
                    if(ans==uu) printf("%d is an ancestor of %d.\n",u,v);
                    else printf("LCA of %d and %d is %d.\n",u,v,b[ans]);
                }
                memset(vs,0,sizeof(vs));
                ans=0;
            }
        }
        return 0;
    }