PAT甲级1151题（LCA问题）

二叉树题

PAT

发布日期: 2021-02-12

文章字数: 323

阅读时长: 1 分

阅读次数:

1.题目介绍

1151

inorder：中序遍历

preorder：先序遍历

distinct：不同的

2.考察点，难度

二叉树类，Map容器插入方法，Vector容器的运用，二叉树遍历，难度中

3.解题代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int u,v;
vector<int> in,pre;
unordered_map<int,int> m;

void LCA(int root, int inL, int inR){
    if(inL>inR) return;
    int rtin=m[pre[root]],vin=m[v],uin=m[u];
    if(rtin==uin) printf("%d is an ancestor of %d.\n",u,v);
    else if(rtin==vin) printf("%d is an ancestor of %d.\n",v,u);
    else if(vin<rtin && uin<rtin) LCA(root+1,inL,rtin-1);
    else if(vin>rtin && uin>rtin) LCA(root+rtin+1-inL,rtin+1,inR);
    else printf("LCA of %d and %d is %d.\n",u,v,pre[root]);
}

int main(){

    int M,N;
    cin>>M>>N;
    in.resize(N);
    pre.resize(N);
    for(int i=0;i<N;i++){
        scanf("%d",&in[i]);
        m.insert({in[i],i});
    }
    for(int i=0;i<N;i++)  scanf("%d",&pre[i]);
    for(int i=0;i<M;i++){
        cin>>u>>v;
        if(m.find(u)==m.end() && m.find(v)==m.end()) printf("ERROR: %d and %d are not found.\n",u,v);
        else if(m.find(u)==m.end())  printf("ERROR: %d is not found.\n",u);
        else if(m.find(v)==m.end())  printf("ERROR: %d is not found.\n",v);
        else LCA(0,0,N-1);
    }
    return 0;
}