题目粗心：
给定一颗含有N个节点的前序和中序序列，要求给定任意2个节点，须要输入其最近公共先人。
算法思路：
这里和1143一样给出2种思路，一种不必建树，一种须要建树。
算法思路1(不必建树)：
咱们借鉴建树的递归过程实现树的局部搜寻，如果以后搜寻的子树的根节点和查问节点U和V相等，阐明其中之一就是先人，间接保留并返回即可，否则获取U和V是否在左子树或者右子树的标记，如果都在左子树，那么就都往左子树搜寻，如果都在右子树，那么就都往右子树搜寻，否则阐明以后子树的根节点就是U和V的最近公共先人，间接保留并返回即可，具体做法就是，在输出中序序列的时候，应用pos保留每一个节点在中序遍历序列中的地位，那么每一次递归查找中序序列根节点的地位就能够替换为int k = pos[pre[preL]];而后再应用uInRight和vInRight别离示意U和V是否在右子树，true示意在右子树，获取的办法也很简略，就是pos[U]>k和pos[V]>k即可，而后再依据uInRight和vInRight的值，要么递归搜寻，要么保留先人ancestor = pre[preL];并返回即可。
算法思路2(建树)：
首先依据前序和中序建设一颗二叉树，而后利用层序遍历的办法取得每一个节点的父亲和其所在层数，对于输出的节点x和y，如果节点所在层数一样，那么只有两者不相等就一起向上搜寻，直到相遇，其相遇节点即为最近公共先人，否则让层数更大的那个先向上走，直到和另外一个节点层数雷同，而后再同时向上，直到相遇为止。
留神点：
- 1、对于算法思路一呈现的测试点4超时景象，须要应用pos记录每一个节点在中序序列的地位，这是要害。
提交后果：
AC代码1（举荐）：
#include<cstdio>using namespace std;const int maxn = 0x3ffffff;int N,M;// 节点数目和测试数目int pre[maxn],in[maxn];bool isValid[maxn];int pos[maxn];// 每一个节点在中序序列中的下标，不会超时的要害void createTree(int preL,int preR,int inL,int inR,int &ancestor,int U,int V){ if(preL>preR) return; if(pre[preL]==U||pre[preL]==V){ ancestor = pre[preL]==U?U:V; return ; } // 找到根节点在中序序列中的地位 int k = pos[pre[preL]];// 间接获取地位 int numOfLeft = k-inL;// 左子树节点个数 bool uInRight = pos[U]>k,vInRight = pos[V]>k;// U和V在左子树还是右子树，true在右子树 if(uInRight&&vInRight){ // U和V都在右子树 createTree(preL+numOfLeft+1,preR,k+1,inR,ancestor,U,V); } else if(!uInRight&&!vInRight){ // U和V都在左子树 createTree(preL+1,preL+numOfLeft,inL,k-1,ancestor,U,V); } else { // U和V别离在左右子树 ancestor = pre[preL]; return; }}int main(){ scanf("%d %d",&M,&N); for (int i = 0; i < N; ++i) { scanf("%d",&in[i]); isValid[in[i]] = true; pos[in[i]] = i; } for (int i = 0; i < N; ++i) { scanf("%d",&pre[i]); } for (int j = 0; j < M; ++j) { int u,v; scanf("%d %d",&u,&v); if(!isValid[u]&&!isValid[v]){ printf("ERROR: %d and %d are not found.\n",u,v); } else if(!isValid[u]){ printf("ERROR: %d is not found.\n",u); } else if(!isValid[v]){ printf("ERROR: %d is not found.\n",v); } else { int ancestor = -1; createTree(0,N-1,0,N-1,ancestor,u,v); if (ancestor==u||ancestor==v){ printf("%d is an ancestor of %d.\n",ancestor,ancestor==u?v:u); } else { printf("LCA of %d and %d is %d.\n",u,v,ancestor); } } } return 0;}AC代码2：
#include<cstdio>#include<string>#include<cstring>#include<iostream>#include<queue>#include<algorithm>using namespace std;struct node{ int data; int level; node* lchild; node* rchild; node* parent; }; const int maxn = 200005;int pre[maxn],in[maxn];int Hash[maxn];//PAT不能用hash node* preN[maxn];int num = 0;//先序遍历下标 node* newNode(int x){ node* w = new node; w->data =x; w->level = 1; w->lchild=w->rchild=w->parent=NULL; return w;}//依据以后子树的前序排序序列和中序排序序列构建二叉树 node* create(int preL,int preR,int inL,int inR){ if(preL>preR){//以后子树为空，没有结点 return NULL; } node* root = newNode(pre[preL]); //首先找到中序遍历序列中等于以后根结点的值得下标 int i; for(i=inL;i<=inR;++i){ if(in[i]==pre[preL]){ break; } } int numLeft = i-inL; //往左子树插入,左子树先序遍历区间为[preL+1,preL+numleft],中序遍历区间为[inL,i-1] root->lchild = create(preL+1,preL+numLeft,inL,i-1); //往右子树插入,右子树先序遍历区间[preL+numLeft+1,preR],中序遍历区间为[i+1,inR] root->rchild = create(preL+numLeft+1,preR,i+1,inR); return root;}//先序遍历void tre(node* root){ if(root==NULL) return; preN[num++] = root; tre(root->lchild); tre(root->rchild);} //层序遍历void layerOrder(node* root){ queue<node*> q; q.push(root); while(!q.empty()){ node* w = q.front(); q.pop(); if(w->lchild!=NULL){ w->lchild->level = w->level+1; w->lchild->parent = w; q.push(w->lchild); } if(w->rchild!=NULL){ w->rchild->level = w->level+1; w->rchild->parent = w; q.push(w->rchild); } }} int main(){ int m,n;//测试的结点对数和结点数目 scanf("%d %d",&m,&n); memset(Hash,0,sizeof(Hash)); for(int i=0;i<n;++i){ scanf("%d",&in[i]); } for(int i=0;i<n;++i){ scanf("%d",&pre[i]); Hash[pre[i]] = i+1; } node* root = create(0,n-1,0,n-1); layerOrder(root); //先序遍历 tre(root); //测试 int x,y; for(int i=0;i<m;++i){ scanf("%d %d",&x,&y); if(Hash[x]!=0&&Hash[y]!=0){ //均是树中结点 node* w1 = preN[Hash[x]-1];//通过结点的值找到前序遍历数组的下标，而后再找到对应结点 node* w2 = preN[Hash[y]-1]; if(w1->level==w2->level){ //2个结点在同一层 if(w1==w2){ printf("%d is an ancestor of %d.\n",x,y); } else{ //2结点不相等，则同时往上走 node* t1 = w1; node* t2 = w2; while(t1->parent!=NULL){ t1 = t1->parent; t2 = t2->parent; if(t1==t2){ printf("LCA of %d and %d is %d.\n",x,y,t1->data); break; } } } }else{ //2结点不在同一层,让层数较大的先往上走 node* max = w1->level>w2->level?w1:w2; node* min = w1->level<w2->level?w1:w2; while(max->level!=min->level&&max->parent!=NULL){ max = max->parent; } //而后判断min是否和max相等 if(min==max){ //阐明min是max的先人,但此时max曾经更改所以得从新赋值 max = w1->level>w2->level?w1:w2; printf("%d is an ancestor of %d.\n",min->data,max->data); } else{ //2结点不相等，则同时往上走 while(max->parent!=NULL){ max = max->parent; min = min->parent; if(max==min){ printf("LCA of %d and %d is %d.\n",x,y,min->data); break; } } } } }else if(Hash[x]==0&&Hash[y]!=0){ printf("ERROR: %d is not found.\n",x); }else if(Hash[x]!=0&&Hash[y]==0){ printf("ERROR: %d is not found.\n",y); }else{ printf("ERROR: %d and %d are not found.\n",x,y); } } return 0;}