PAT甲级1151 LCA in a Binary Tree LCA+DFS-蒲公英云

PAT甲级1151 LCA in a Binary Tree LCA+DFS

清疚 2023-02-21 06:51 124阅读 0赞

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70

LCA问题在常规树中的实现，思路和1143一样，本体主要要解决的就是递归子树边界的问题

我采用的map映射的方法，将中序遍历的结点值映射为下标位置，那么如果用下标来代替结点值的话，当前的树便是一颗bst树了

利用这个特性，比较映射值便可以判断左右子树的关系

#include<iostream>
#include<vector>
#include<unordered_map>
#include<cstdio>
using namespace std;
vector<int> pre,in;
unordered_map<int,int> indexofbst;//映射的二叉搜索树下标
void dfs(int root,int l,int r,int a,int b)//root为当前根结点在先序中下标
{
    //if(l>r)return;//递归边界
    int ia=indexofbst[a],ib=indexofbst[b];//测试的点在中序中的下标
    int iroot=indexofbst[pre[root]];//根结点在中序下标
    if((ia<iroot&&ib>iroot)||(ia>iroot&&ib<iroot))//在根结点的两侧
        printf("LCA of %d and %d is %d.\n",a,b,pre[root]);
    else if(ia<iroot&&ib<iroot)//都在左子树
        dfs(root+1,l,iroot-1,a,b);
    else if(ia>iroot&&ib>iroot)//递归中序右子树区间
        dfs(root+iroot,iroot+1,r,a,b);
    else if(ia==iroot)printf("%d is an ancestor of %d.\n",a,b);
    else printf("%d is an ancestor of %d.\n",b,a);
}
int main()
{
    int n,m;//n结点数,m测试样例数
    cin>>m>>n;
    pre.resize(n+1);
    in.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>in[i];
        indexofbst[in[i]]=i;
    }
    for(int i=1;i<=n;i++) 
    {
        cin>>pre[i];
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(!indexofbst[a]&&!indexofbst[b])
        printf("ERROR: %d and %d are not found.\n",a,b);
        else if(!indexofbst[a])
        printf("ERROR: %d is not found.\n",a);
        else if(!indexofbst[b])
        printf("ERROR: %d is not found.\n",b);
        else 
        {
            dfs(1,1,n,a,b);
        }
    }
    return 0;
}