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

题目链接：

题目大意：给出中序序列和先序序列，再给出两个点，求这两个点的最近公共祖先。

解题思路：不用建树～已知某个树的根结点，若a和b在根结点的左边，则a和b的最近公共祖先在当前子树根结点的左子树寻找，如果a和b在当前子树根结点的两边，在当前子树的根结点就是a和b的最近公共祖先，如果a和b在当前子树根结点的右边，则a和b的最近公共祖先就在当前子树的右子树寻找。中序加先序可以唯一确定一棵树，在不构建树的情况下，在每一层的递归中，可以得到树的根结点，在此时并入lca算法可以确定两个结点的公共祖先～

注意：题目中 n 才是结点个数；pos 不能用数组开，因为存储位置的是利用该结点的值而不是下标，所以用ump。

AC 代码1（未建树版）

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn=1e4+10;int in[maxn], pre[maxn];unordered_map
     
       pos;void lca(int inl,int inr,int prel,int a,int b){    if(inl>inr) return;    int inRt=pos[pre[prel]], aIn=pos[a], bIn=pos[b];    if(inRt>aIn && inRt
      
       bIn) printf("LCA of %d and %d is %d.\n", a, b, in[inRt]);    else if(aIn==inRt || bIn==inRt) printf("%d is an ancestor of %d.\n", in[inRt], aIn==inRt ? b : a);    else if(aIn>inRt && bIn>inRt) lca(inRt+1,inr,prel+1+(inRt-inl),a,b);    else if(aIn
      
     
    
   

AC 代码2（建树-搜索版）

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn=1e4+10;struct node{    int d,l,r;}T[maxn];unordered_map
     
       vis;int in[maxn], pre[maxn];int create(int l1,int r1,int l2,int r2) // in pre{    if(l1>r1) return -1;    int rt=l2;    int p1=l1,p2;    while(in[p1]!=pre[rt]) p1++;    p2=p1-l1;    T[rt].d=pre[rt];    T[rt].l=create(l1,p1-1,l2+1,l2+p2);    T[rt].r=create(p1+1,r1,l2+p2+1,r2);    return rt;}int lca(int rt,int a,int b){    if(rt==-1) return -1;    if(a==T[rt].d || b==T[rt].d) return rt;    int left=lca(T[rt].l,a,b);    int right=lca(T[rt].r,a,b);    if(left!=-1 && right!=-1) return rt;    return left==-1 ? right : left;}int main(){    int n,q,a,b;    scanf("%d%d",&q,&n);    for(int i=0;i
     
    
   

AC 代码3（建树-LCA版）

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn=1e4+10;struct node{    int d,l,r;}T[maxn];unordered_map
     
       vis, lvl, fu;int in[maxn], pre[maxn];int create(int l1,int r1,int l2,int r2,int l,int f) // in pre{    if(l1>r1) return -1;    int rt=l2;    int p1=l1,p2;    while(in[p1]!=pre[rt]) p1++;    p2=p1-l1;    T[rt].d=pre[rt];    lvl[pre[rt]]=l;    fu[pre[rt]]=f;    T[rt].l=create(l1,p1-1,l2+1,l2+p2,l+1,pre[rt]);    T[rt].r=create(p1+1,r1,l2+p2+1,r2,l+1,pre[rt]);    return rt;}int lca(int a,int b){    int root;    if(a==b) return a;    if(fu[a]==fu[b]) return fu[a];    if(lvl[a]>lvl[b]) root=lca(fu[a],b);    else root=lca(a,fu[b]);    if(root!=-1) return root;    return -1;}int main(){    int n,q,a,b;    scanf("%d%d",&q,&n);    for(int i=0;i
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/82621545 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！