PAT甲级1143 Lowest Common Ancestor BST+LCA

╰半橙微兮° 2023-02-21 06:47 25阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70][]

本想建树然后通过递归左右子树的形式去做，但是发现题中说明最多有一万个结点，写完以后果然超时....

# **判别LCA的方法** #

**判断当前的两个点的位置情况，如果一个在左子树，一个在右子树，那么根便是最小公共祖先；**

**如果都在左子树，递归左子树判断；如果都在右子树，递归右子树判断；**

**如果一个就是根，那么它便是最小公共祖先**

# 解决超时方法： #

由于题目告知是bst树，其实只需要比较结点值便可以确定左右子树的关系。但是递归时根结点的判断比较麻烦。主要有如下两种情况：

**1.都在左子树，那么左子树的根下标就是当前的根下标+1（先序遍历特点）**

**2.如果在右子树，这时就需要循环遍历所有结点，找到第一个比根大的，它就是右子树的根**

# 几大坑点： #

1.题目背景描述中说右子树是大于等于根，所以我判断的时候就加了等号，下面的输入输出中又说了结点值都不相同，按理应该没毛病，结果两测试点不过，改回来就好。。。

2.找根的时候我一开始是从右往左找，最后一个测试点超时，改成从左往右就好了，应该是测试数据的问题，很蛇皮

#include<iostream>
    #include<vector>
    #include<map>
    using namespace std;
    vector<int> pre;
    int m,n;
    map<int,bool> h;//结点是否出现
    int findright(int value,int index)
    {
        int i;
        for(i=index+1;i<n;i++)
        {
            if(pre[i]>value)break;
        }
        return i;
    }
    void lca(int root,int a,int b)//root为当前根结点的在先序的下标位置
    {
        //if(root<0||root>n)return;
        if((a<pre[root]&&b>pre[root])||(a>pre[root]&&b<pre[root]))printf("LCA of %d and %d is %d.\n",a,b,pre[root]);
        else if(a<pre[root]&&b<pre[root])lca(root+1,a,b);
        else if(a>pre[root]&&b>pre[root])lca(findright(pre[root],root),a,b);
        else if(pre[root]==a)printf("%d is an ancestor of %d.\n",a,b);
        else printf("%d is an ancestor of %d.\n",b,a);
    }
    int main()
    {
        //int m,n;
        cin>>m>>n;
        pre.resize(n);
        for(int i=0;i<n;i++){cin>>pre[i];h[pre[i]]=true;}
        int a,b;
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            if(!h[a]&&!h[b])printf("ERROR: %d and %d are not found.\n",a,b);
            else if(!h[a])printf("ERROR: %d is not found.\n",a);
            else if(!h[b])printf("ERROR: %d is not found.\n",b);
            else lca(0,a,b);
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629162641294.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70