乐趣区

关于算法-数据结构:PAT甲级1151-LCA-in-a-Binary-Tree

题目粗心:

给定一颗含有 N 个节点的前序和中序序列,要求给定任意 2 个节点,须要输入其最近公共先人。

算法思路:

这里和 1143 一样给出 2 种思路,一种不必建树,一种须要建树。

算法思路 1(不必建树):

咱们借鉴建树的递归过程实现树的局部搜寻,如果以后搜寻的子树的根节点和查问节点 U 和 V 相等,阐明其中之一就是先人,间接保留并返回即可,否则获取 U 和 V 是否在左子树或者右子树的标记,如果都在左子树,那么就都往左子树搜寻,如果都在右子树,那么就都往右子树搜寻,否则阐明以后子树的根节点就是 U 和 V 的最近公共先人,间接保留并返回即可,具体做法就是,在输出中序序列的时候,应用 pos 保留每一个节点在中序遍历序列中的地位,那么每一次递归查找中序序列根节点的地位就能够替换为int k = pos


];而后再应用 uInRight 和 vInRight 别离示意 U 和 V 是否在右子树,true 示意在右子树,获取的办法也很简略,就是 pos[U]>kpos[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

];// 间接获取地位
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

] = 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;
}


退出移动版