PAT甲级1143.

目录

A1143

题目

样例

输入:

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

输出:

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

思路和坑点

　　思路:
　　题目给出的是二叉搜索树的先序遍历，可以根据二叉搜索树的特性来查找，具体原理参见代码注释，要留意题目给出的数据结构的特性，并加以利用。

AC代码

#include<bits/stdc++.h>
using namespace std; 
unordered_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];                                 //判断每一个结点和uv的关系
            if ((a >= u && a <= v) || (a >= v && a <= u)) break;//根据先序的顺序规律，当U和V出现在a的左右两侧或者某个在a的位置上时，a是公共祖先
        }
        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;
}