共计 3841 个字符，预计需要花费 10 分钟才能阅读完成。
题目粗心：
给定一颗二叉排序树的先序序列，输入待查问的两个节点的最近公共先人。
算法思路 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] = 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&¬_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] = 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;
}
