题目粗心：

给定一颗二叉排序树的先序序列，输入待查问的两个节点的最近公共先人 。

算法思路1(不建树)：

应用$pre$寄存输出的先序序列，$isLegal$标记每一个树中的节点，对于输出的节点只有小于0或者$isLegal$对应值为false，就阐明不在树中，输入对应的$ERROR$信息，都在就在先序序列中进行搜寻，假如输出的结点为$a$和$b$，那么对应$a$和$b$的所有先人肯定是在先序序列中从左向右顺次排列，那么第一次在先序序列中呈现的先人就是$a$和$b$的最近公共先人，对于$a$和$b$的先人，肯定是在$a$和$b$之间，也就是处在$[a,b]$或者$[b,a]$之中，所以，咱们须要做的事件就是遍历一遍pre数组，找到第一个处于$[a,b]$或者$[b,a]$之间的结点$ans$，而后进行输入即可。

算法思路2(建树)：

首先依据二叉查找树的前序序列构建二叉排序树 ，对建设好的二叉查找树进行层序遍历,初始化每个结点的档次和父节点，首先对于2个档次不同的结点A和B，layer=max(Alayer,Blayer)，则先人肯定不在layer层上，那么先查看min(Alayer,Blayer) 层上的结点是否是另外一个结点的先人，也就是只有 Alayer！=Blayer，层数较大者始终往上走，如果层数相等后恰好为其中一个结点，则该结点就是最小公共先人，否则2个结点同时向上走，晓得走到同一结点或者到NULL。

留神点：

  • 1、结点的数值能够大于100000，所以isLegal数组大小最小为193313，否则测试点2会呈现段谬误。

提交后果：

AC代码1：

#include<cstdio>using namespace std;struct Node{    int data;    Node *left;    Node *right;};int pre[100005];// 先序序列bool isLegal[193313];// 标记树中的每一个结点,过小会导致测试点2段谬误 int main(){    int M,N;// 查问数目和结点数目     scanf("%d %d",&M,&N);    for(int i=0;i<N;++i){        scanf("%d",&pre[i]);        isLegal[pre[i]] = true;    }    int a,b;    for(int i=0;i<M;++i){        scanf("%d %d",&a,&b);        bool not_legal_a = a<0?true:!isLegal[a];        bool not_legal_b = b<0?true:!isLegal[b];        if(not_legal_a&&not_legal_b){            printf("ERROR: %d and %d are not found.\n",a,b);        }else if(not_legal_a){            printf("ERROR: %d is not found.\n",a);        }else if(not_legal_b){            printf("ERROR: %d is not found.\n",b);        }else{            // a和b都在树中            int ans;            for(int i=0;i<N;++i){                if((pre[i]>=a&&pre[i]<=b)||(pre[i]>=b&&pre[i]<=a)){                    ans = pre[i];                    break;                }            }             if(ans==a){                // a是b的先人                 printf("%d is an ancestor of %d.\n",ans,b);             }else if(ans==b){                // b是a的先人                printf("%d is an ancestor of %d.\n",ans,a);            }else {                printf("LCA of %d and %d is %d.\n",a,b,ans);             }        }    }    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];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){    if(preL>preR){//以后子树为空，没有结点         return NULL;    }    node* root = newNode(pre[preL]);    //首先找到第一个大于以后子树根结点的地位i    int i;    for(i=preL+1;i<=preR;++i){        if(root->data<pre[i]){            break;        }    }     //往左子树插入,左子树范畴为[preL+1,k-1]     root->lchild = create(preL+1,i-1);    //往右子树插入,右子树范畴为[k,preR]    root->rchild = create(i,preR);    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",&pre[i]);        Hash[pre[i]] = i+1;    }    node* root = create(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;}