本文共 1348 字，大约阅读时间需要 4 分钟。

【题意】

给定一棵树的中序和前序，给出q个询问，每个询问两个点u,v，询问u,v的最近公共祖先。

【题解】

不需要建整颗树，在左根右这样的中序时，如果两个结点分别在根的左右(可包含根)，那么根即是LCA；如果两个结点同时在根的左边，那么我们继续遍历左子树；否则继续遍历右子树。

【代码】

#include 
   
    using namespace std;const int N=10005;unordered_map 
    
      mp;unordered_map 
     
       mp2;int in[N];int pre[N];int ans;int a,b;void dfs(int midl,int midr,int prel,int prer){    int root=pre[prel];    int p=mp[root];    if(a<=p&&b>=p){        ans=in[p]; return;    }    else if(a<=p&&b<=p){ //左        dfs(midl,p-1,prel+1,prel+(p-midl));    }    else{        dfs(p+1,midr,prel+(p-midl)+1,prer);    }}int main(){    int m,n; scanf("%d%d",&m,&n);    for(int i=1;i<=n;i++) scanf("%d",&in[i]),mp[in[i]]=i;    for(int i=1;i<=n;i++) scanf("%d",&pre[i]);    while(m--){        int x,y; scanf("%d%d",&x,&y);        if(mp.count(x)) a=mp[x];        else a=-1;        if(mp.count(y)) b=mp[y];        else b=-1;        if(a==-1&&b==-1) printf("ERROR: %d and %d are not found.\n",x,y);        else if(a==-1) printf("ERROR: %d is not found.\n",x);        else if(b==-1) printf("ERROR: %d is not found.\n",y);        else{            if(a>b) swap(a,b);            dfs(1,n,1,n);            if(ans==x) printf("%d is an ancestor of %d.\n",x,y);            else if(ans==y) printf("%d is an ancestor of %d.\n",y,x);            else printf("LCA of %d and %d is %d.\n",x,y,ans);        }    }    return 0;}
     
    
   

转载地址：http://rhfen.baihongyu.com/