目录

解法一思路

结果

解法一改进

解法一改进结果

​解法二思路

解法一代码

解法一改进代码

解法二代码(AC)

解法一思路

1. 根据先序和中序建树

2. 对树进行深度优先遍历，找到每一个结点的父节点(注意：由于值的范围是int，直接用可能导致溢出，所以采用值在中序/先序中的下标来映射)

3. 对于读入的值，先判断有没有出现过，如果都出现过，分别得到两个结点的祖先序列(顺序是从自身到根节点)，然后进行双循环比对。最后将得到的结点分别和两个输入值比较来输出结果。

结果

最后两个用例超时

解法一改进

我觉得运行超时是因为最后的双循环复杂度高了再加外层循环，试图加入一个哈希，把双循环变成单循环。

主要改动如下

		int anc;		for(int i = pre[v1].size()-1;i>=0;i--){anc = pre[v1][i];if(preMp[inPos[v2]][inPos[anc]] == 1)break;}

解法一改进结果

 解法二思路

参考了这篇博客 外链 给出的求解LCA的通法，终于AC了。

1. 在结点结构体中加入父节点属性

struct Node{int v;Node *lchild,*rchild,*pa;
};

2. 封装求系谱(包含自身)长度的函数

int getLinkLen(Node* childNode){int ll = 1;while(childNode->pa){childNode = childNode->pa;ll ++;}return ll; 
}

3. 求最近祖先节点的函数

3.1 分别求出结点p和q系谱链的长度

3.2 把更长的一方缩短到和另一方一样长(也许此时两个点已经重合)

3.3 两方同时回溯，直到遇到相同祖先

Node* getLCA(Node* p,Node* q){int pLen = getLinkLen(p);int qLen = getLinkLen(q);while(pLen<qLen){q = q->pa;qLen --;}while(qLen<pLen){p = p->pa;pLen --;}while(p!=q){p = p->pa;q = q->pa;}return p;
}

4. 在建树的过程中新增

4.1 给每个非空结点指明父节点

4.2 由于题目的输入是数值，而getLCA的参数是Node*类型，所以要有int->Node*的映射。

4.3 由于题目的输出是数值，而getLCA的返回值是Node*类型，所以要有Node*->int的映射。

Node* create(int inL,int inR,int preL,int preR){if(preL>preR)return NULL;Node* root = new Node;root->v = preSq[preL];vmp[root] = root->v;nmp[root->v] = root;int k;for(k=inL;k<=inR;k++){if(inSq[k]==root->v)break;}int leftnum = k-inL;root->lchild = create(inL,k-1,preL+1,preL+leftnum);if(root->lchild)root->lchild->pa = root;root->rchild = create(k+1,inR,preL+leftnum+1,preR);if(root->rchild)root->rchild->pa = root;return root;
}

解法一代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<map>
#include<vector>
#include<set>using namespace std;const int maxn = 10001;
const int SUP = 2000000000;int inSq[maxn],preSq[maxn];//set<int> st;
map<int,int> appmp;map<int,int> vToIdx;int pre[maxn];//下标为inIdx vector<int> vi,vi1,vi2;struct Node{int v;Node *lchild,*rchild;
}; void getAncest(int idx){while(pre[idx]!=idx){vi.push_back(inSq[idx]);idx = pre[idx];}return;
}Node* create(int inL,int inR,int preL,int preR){if(preL>preR)return NULL;Node* root = new Node;root->v = preSq[preL];int k;for(k=inL;k<=inR;k++){if(inSq[k]==root->v)break;}int leftnum = k-inL;root->lchild = create(inL,k-1,preL+1,preL+leftnum);root->rchild = create(k+1,inR,preL+leftnum+1,preR);return root;
}void DFS(Node* root){if(root==NULL)return;if(root->lchild!=NULL){int sonIdx = vToIdx[root->lchild->v];pre[sonIdx]= vToIdx[root->v];DFS(root->lchild);}if(root->rchild!=NULL){int sonIdx = vToIdx[root->rchild->v];pre[sonIdx]= vToIdx[root->v];DFS(root->rchild);}return;
}int main(){int pair,n;cin>>pair>>n;for(int i=0;i<n;i++){cin>>inSq[i];appmp[inSq[i]] = 1;vToIdx[inSq[i]] = i;}for(int i=0;i<n;i++){cin>>preSq[i];}Node* root = create(0,n-1,0,n-1);int ridx = vToIdx[root->v];pre[ridx] = ridx;DFS(root);while(pair--){int v1,v2;cin>>v1>>v2;if(appmp[v1]==0){if(appmp[v2]==0){printf("ERROR: %d and %d are not found.\n",v1,v2);continue;}else{printf("ERROR: %d is not found.\n",v1);continue;}}else{if(appmp[v2]==0){printf("ERROR: %d is not found.\n",v2);continue;}}vi.clear(); getAncest(vToIdx[v1]);vi1 = vi;vi1.push_back(root->v);vi.clear();getAncest(vToIdx[v2]);vi2 = vi;vi2.push_back(root->v);	bool gotit = false;int LCA;for(int i=0;i<vi1.size()&&gotit==false;i++){for(int j=0;j<vi2.size();j++){if(vi1[i]==vi2[j]){LCA = vi1[i];gotit = true;break;}}}if(LCA==v1){printf("%d is an ancestor of %d.\n",v1,v2);}else if(LCA==v2){printf("%d is an ancestor of %d.\n",v2,v1);}else{printf("LCA of %d and %d is %d.\n",v1,v2,LCA);}}return 0;
}

解法一改进代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<time.h>
#include<vector>
#include<set>
#include<string>using namespace std;
typedef long long LL;const int maxn = 10007;
const int MOD = 1000000007;
const int INF = 1000000000;//INF:下确界  
const LL SUP = (1LL<<63)-1;//SUP:上确界 
const double eps = 1e-5;int inSq[maxn],preSq[maxn];
int inPos[maxn];
int n;map<int,int> eximp;map<int,vector<int> > pre;map<int,map<int,int> > preMp;struct Node{int v;Node *lchild,*rchild;
};Node* create(int inL,int inR,int preL,int preR){if(preL>preR)return NULL;Node* root = new Node;root->v = preSq[preL];int k;for(k=inL;k<=inR;k++){if(inSq[k]==root->v)break;}int leftnum = k-inL;root->lchild = create(inL,k-1,preL+1,preL+leftnum);root->rchild = create(k+1,inR,preL+leftnum+1,preR);return root;
}void DFS(Node* root){if(root==NULL)return;pre[root->v].push_back(root->v);preMp[inPos[root->v]][inPos[root->v]] = 1;if(root->lchild!=NULL){pre[root->lchild->v] = pre[root->v];preMp[inPos[root->lchild->v]] = preMp[inPos[root->v]];DFS(root->lchild);}if(root->rchild!=NULL){pre[root->rchild->v] = pre[root->v];preMp[inPos[root->rchild->v]] = preMp[inPos[root->v]];DFS(root->rchild);}
}int main(){int pNum;cin>>pNum>>n;for(int i=0;i<n;i++){cin>>inSq[i];eximp[inSq[i]] = 1;inPos[inSq[i]] = i;}for(int i=0;i<n;i++){cin>>preSq[i];}Node* root = create(0,n-1,0,n-1);DFS(root);while(pNum--){int v1,v2;cin>>v1>>v2;if(eximp[v1]==0||eximp[v2]==0){if(eximp[v1]==1)printf("ERROR: %d is not found.\n",v2);else if(eximp[v2]==1)printf("ERROR: %d is not found.\n",v1);else printf("ERROR: %d and %d are not found.\n",v1,v2);continue;}int anc;		for(int i = pre[v1].size()-1;i>=0;i--){anc = pre[v1][i];if(preMp[inPos[v2]][inPos[anc]] == 1)break;}if(anc==v1||anc==v2){printf("%d is an ancestor of %d.\n",anc==v1?v1:v2,anc==v1?v2:v1);}else  printf("LCA of %d and %d is %d.\n",v1,v2,anc);}return 0;
}

解法二代码(AC)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<time.h>
#include<vector>
#include<set>
#include<string>using namespace std;
typedef long long LL;const int maxn = 10007;
const int MOD = 1000000007;
const int INF = 1000000000;//INF:下确界  
const LL SUP = (1LL<<63)-1;//SUP:上确界 
const double eps = 1e-5;int inSq[maxn],preSq[maxn];
int n;map<int,int> eximp;struct Node{int v;Node *lchild,*rchild,*pa;
};map<Node*,int> vmp;
map<int,Node*> nmp;Node* create(int inL,int inR,int preL,int preR){if(preL>preR)return NULL;Node* root = new Node;root->v = preSq[preL];vmp[root] = root->v;nmp[root->v] = root;int k;for(k=inL;k<=inR;k++){if(inSq[k]==root->v)break;}int leftnum = k-inL;root->lchild = create(inL,k-1,preL+1,preL+leftnum);if(root->lchild)root->lchild->pa = root;root->rchild = create(k+1,inR,preL+leftnum+1,preR);if(root->rchild)root->rchild->pa = root;return root;
}int getLinkLen(Node* childNode){int ll = 1;while(childNode->pa){childNode = childNode->pa;ll ++;}return ll; 
} Node* getLCA(Node* p,Node* q){int pLen = getLinkLen(p);int qLen = getLinkLen(q);while(pLen<qLen){q = q->pa;qLen --;}while(qLen<pLen){p = p->pa;pLen --;}while(p!=q){p = p->pa;q = q->pa;}return p;
}int main(){int pNum;cin>>pNum>>n;for(int i=0;i<n;i++){cin>>inSq[i];eximp[inSq[i]] = 1;}for(int i=0;i<n;i++){cin>>preSq[i];}Node* root = create(0,n-1,0,n-1);while(pNum--){int v1,v2;cin>>v1>>v2;if(eximp[v1]==0||eximp[v2]==0){if(eximp[v1]==1)printf("ERROR: %d is not found.\n",v2);else if(eximp[v2]==1)printf("ERROR: %d is not found.\n",v1);else printf("ERROR: %d and %d are not found.\n",v1,v2);continue;}Node* p = nmp[v1];Node* q = nmp[v2];int LCA = vmp[getLCA(p,q)];if(LCA==v1||LCA==v2)printf("%d is an ancestor of %d.\n",LCA==v1?v1:v2,LCA==v1?v2:v1);else printf("LCA of %d and %d is %d.\n",v1,v2,LCA);}return 0;
}