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

1143

題目：

BST構建，LCA判斷惕虑，前序遍歷

范圍:

結點數(shù)N < 10000
判斷數(shù)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; 
}

網(wǎng)上完美答案（相當簡潔而且只有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;
}