PAT甲级 1151 LCA in a Binary Tree (30分) 最近公共祖先

PAT甲级 1151 LCA in a Binary Tree (30分) 最近公共祖先

题目大意：

给出中序序列和先序序列，再给出两个点，求这两个点的最近公共祖先

不建树的做法：

已知某个树的根结点，若a和b在根结点的左边，则a和b的最近公共祖先在当前子树根结点的左子树寻找，如果a和b在当前子树根结点的两边，在当前子树的根结点就是a和b的最近公共祖先，如果a和b在当前子树根结点的右边，则a和b的最近公共祖先就在当前子树的右子树寻找。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 10020
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

map<int,int> pos;//记录中序中的节点的位置
int in[MAX],pre[MAX];//中序和前序
int n,m,a,b;

void lca(int inl,int inr,int preroot,int a,int b) {//l和r为中序中的位置
    if(inl>inr) return;
    int inroot=pos[pre[preroot]];//inroot为中序中根节点的位置
    int ain=pos[a],bin=pos[b];
    if(ain<inroot&&bin<inroot){//若a和b都在左子树中
        lca(inl,inroot-1,preroot+1,a,b);
    }else if((ain<inroot&&bin>inroot)||(ain>inroot&&bin<inroot)){//若a和b一个在左子树，一个在右子树
        printf("LCA of %d and %d is %d.\n",a,b,in[inroot]);
    }else if (ain>inroot&&bin>inroot){//若a和b都在右子树中
        lca(inroot+1,inr,preroot+1+(inroot-inl),a,b);
    }else if(ain==inroot){
            printf("%d is an ancestor of %d.\n",a,b);
    }else if (bin==inroot){
            printf("%d is an ancestor of %d.\n",b,a);
    }
}

int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&in[i]);
        pos[in[i]]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&pre[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        if(pos[a]==0&&pos[b]==0){
            printf("ERROR: %d and %d are not found.\n",a,b);
        }else if(pos[a]==0||pos[b]==0){
            printf("ERROR: %d is not found.\n",pos[a]==0?a:b);
        }else{
            lca(1,n,1,a,b);
        }
    }
    return 0;
}

建树的做法：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 10020
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

struct node{
    int key;
    node* left;
    node *right;
};

map<int,int> mp;//记录中序中的节点的位置
int in[MAX],pre[MAX];//中序和前序
int n,m,a,b;

node* build_tree(int r,int start,int ends){
    if(start>ends){
        return NULL;
    }
    int i=start;
    while(i<ends&&in[i]!=pre[r]){
        i++;
    }
    node* root=(node *)malloc(sizeof(node));
    root->key=pre[r];
    root->left=build_tree(r+1,start,i-1);//遍历左子树
    root->right=build_tree(r+1+i-start,i+1,ends);//遍历右子树
    return root;
}

node* lca(node* root,int a,int b){//lca算法
    if(root==NULL||root->key==a||root->key==b) return root;
    node* L=lca(root->left,a,b);
    node* R=lca(root->right,a,b);
    if(L==NULL) return R;
    if(R==NULL) return L;
    return root;
}

int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&in[i]);
        mp[in[i]]=1;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&pre[i]);
    }
    node *root=build_tree(1,1,n);//建立二叉树
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        if(mp[a]==0&&mp[b]==0){
            printf("ERROR: %d and %d are not found.\n",a,b);
        }else if(mp[a]==0){
            printf("ERROR: %d is not found.\n",a);
        }else if(mp[b]==0){
            printf("ERROR: %d is not found.\n",b);
        }else{
            node *res=lca(root,a,b);
            if(res->key==a){
                printf("%d is an ancestor of %d.\n",a,b);
            }else if(res->key==b){
                printf("%d is an ancestor of %d.\n",b,a);
            }else{
                printf("LCA of %d and %d is %d.\n",a,b,res->key);
            }
        }
    }
    return 0;
}