PAT甲级1143Lowest Common Ancestor

Posted on | | Visitors:
Words count in article: 611 字 | Reading time ≈ 3 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805343727501312

题解

题目要求

  • 最近公共祖先（LCA，The lowest common ancestor）

    在一颗树中，结点U和V的LCA是U和V为其后代的深度最大的结点。

  • 二叉搜索树（BST，binary search tree）

    • 树中的每个结点的值都大于其左子树中结点的值
    • 树中的每个结点的值都不超过其右子树中结点的值
    • 每个结点的左子树和右子树都是二叉搜索树

给定一个二叉搜索树中的任意两个结点，请找到他们的LCA。

  • 输入

    • M：正整数，不超过1000，需要测试的结点对的数量
    • N：正整数，不超过10000，二叉搜索树中结点的数量
    • N个结点（互异）：按照先序遍历的顺序给出，值都在int范围内
    • M个结点对

  • 输出

    对于每个结点对，判断结点对中每个结点是否存在，如果都存在则找到他们的LCA。

解题思路

不需建树

  • 判断结点是否在树中

    读取树的先序遍历时使用map记录一个结点是否在树中

  • 寻找LCA

    根据BST的性质，如果一个结点的值处于u和v的值之间，那这个结点就是u和v的LCA。

这道题涉及LCA，也可以看看另外一道题：PAT甲级1151 LCA in a Binary Tree

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Problem: PAT Advanced 1143
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805343727501312
// Tags: Tree BST LCA map

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    int m, n, u, v, a;
    scanf("%d %d", &m, &n);

    vector<int> preOrder(n);
    map<int, bool> exists;
    for (int i = 0; i < n; i++){ // 读取先序遍历结果并记录结点是否出现过
        scanf("%d", &preOrder[i]);
        exists[preOrder[i]] = true;
    }

    while (m--) { // m个结点对
        scanf("%d %d", &u, &v);

        for (int i = 0; i < n; i++){ // 寻找LCA
            a = preOrder[i];
            if (u < a && v > a || v < a && u > a || (a == u) || (a == v) )
                break;
        }

        if (exists[u] == false && exists[v] == false)
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if (exists[u] == false || exists[v] == false)
            printf("ERROR: %d is not found.\n", exists[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;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!