title: PAT1143
date: 2021-01-22 20:03:07
tags: PAT

1143

题目：

BST构建，LCA判断，前序遍历

范围:

结点数N < 10000
判断数M < 1000

分析:

• 实际上BST构建这一步是多的，不需要构建即可知道，前序遍历中LCA必在两个结点的前面
• 如果要在给出的BST查找结点是否存在，会有一个样例超时，因为可能给出的是不平衡的树，所以需要建map查找

解法:

前序遍历判断LCA必在两个结点的前面，所以依次查看前序遍历的结点，找到夹在查找到两个结点大小的点即可退出

代码:

差一个超时样例

#include<iostream>
#include<math.h>
#include<algorithm>

using namespace std; 

struct node{
    int val; 
    int idx; 
    int l_child, r_child; 
};

int M, N; 
node tree[10005]; 

void make_BST(int root){
    if(root == -1) return; 
    int root_val = tree[root].val; 
    int l = -1, r = -1; 
    for(int i = root + 1; i < N; i++){
        if(tree[i].val < root_val){
            l = i;
            break;  
        }
    }
    for(int i = root + 1; i < N; i++){
        if(tree[i].val > root_val){
            r = i;
            break;  
        }
    }
    tree[root].l_child = l; 
    tree[root].r_child = r;
    make_BST(l); 
    make_BST(r); 
    return; 
}

int find_idx(int idx, int val){
    if(idx == -1) return -1; 
    if(val == tree[idx].val) return idx; 
    else if(val < tree[idx].val) {
        return find_idx(tree[idx].l_child, val); 
    }
    else return find_idx(tree[idx].r_child, val); 
    // for(int i = 0; i < N; i++){
    //     if(tree[i].val == val) return i; 
    // }
    // return -1; 
}

void find_ancestor(int u, int v){
    
    int a; 
    for(int i = 0; i < N; i++){
        // cout<<1<<endl; 
        a = tree[i].val; 
        if((a <= u && a >= v) || (a <= v && a >= u)) {
            break;
        }
    }
    if (a == u || a == v) printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
    else printf("LCA of %d and %d is %d.\n", u, v, a);
    return; 
}

int main()
{
    freopen("1143_in", "r", stdin); 
    cin>>M>>N; 
    for(int i = 0; i < N; i++){
        cin>>tree[i].val;
        tree[i].idx = i; 
        tree[i].l_child = -1; 
        tree[i].l_child = -1; 
    }
    make_BST(0); 
    for(int i = 0; i < M; i++){
        int a, b, a_idx, b_idx; 
        cin>>a>>b; 
        a_idx = find_idx(0, a);
        b_idx = find_idx(0, b);
        //Erro print
        if(a_idx == -1 || b_idx == -1){
            if(a_idx == -1 && b_idx == -1) printf("ERROR: %d and %d are not found.\n", a, b); 
            else if(a_idx == -1) printf("ERROR: %d is not found.\n", a); 
            else printf("ERROR: %d is not found.\n", b); 
        }
        else {
            find_ancestor(a, b); 
        }
    }
    return 0; 
}

网上完美答案（相当简洁而且只有30行）

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, bool> mp;
int main() {
    int m, n, u, v, a;
    scanf("%d %d", &m, &n);
    vector<int> pre(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
        mp[pre[i]] = true;
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        for(int j = 0; j < n; j++) {
            a = pre[j];
            if ((a >= u && a <= v) || (a >= v && a <= u)) break;
        } 
        if (mp[u] == false && mp[v] == false)
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if (mp[u] == false || mp[v] == false)
            printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);
        else if (a == u || a == v)
            printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
        else
            printf("LCA of %d and %d is %d.\n", u, v, a);
    }
    return 0;
}