PAT 1143. Lowest Common Ancestor (30)

Posted on Edited on In

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants. A binary search tree (BST) is recursively defined as a binary tree which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Given any two nodes in a BST, you are supposed to find their LCA.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: M (<= 1000), the number of pairs of nodes to be tested; and N (<= 10000), the number of keys in the BST, respectively. In the second line, N distinct integers are given as the preorder traversal sequence of the BST. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.

Output Specification:

For each given pair of U and V, print in a line “LCA of U and V is A.” if the LCA is found and A is the key. But if A is one of U and V, print “X is an ancestor of Y.” where X is A and Y is the other node. If U or V is not found in the BST, print in a line “ERROR: U is not found.” or “ERROR: V is not found.” or “ERROR: U and V are not found.”.

Sample Input:

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

Sample Output:

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.

给出两个结点，找他们的最近的祖先结点。 把所有的结点值放到set中，便于查找没有出现的结点。 如果两个结点的值比当前子树的根结点的值小，则左递归；如果两个结点的值比当前子树的根结点的值大，则右递归。否则，当前子树的根结点就是最近的公共祖先。

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
43
44
45
46
47
48
49
#include <iostream>
#include <set>

using namespace std;

int *pre;

int idx(int l, int r, int x) {
    for (int i = l; i <= r; i++)
        if (pre[i] >= x) return i;
    return -1;
}

int find_lca(int l, int r, int a, int b) {
    if (a < pre[l] && b < pre[l]) return find_lca(l + 1, idx(l + 1, r, pre[l]) - 1, a, b);
    if (a > pre[l] && b > pre[l]) return find_lca(idx(l + 1, r, pre[l]), r, a, b);
    return pre[l];
}

int main() {
    int m = 0, n = 0, a = 0, b = 0;
    scanf("%d %d", &m, &n);
    pre = new int[n + 1];
    set<int> s;
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
        s.insert(pre[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        if (s.find(a) == s.end() && s.find(b) == s.end()) {
            printf("ERROR: %d and %d are not found.\n", a, b);
        } else if (s.find(a) == s.end()) {
            printf("ERROR: %d is not found.\n", a);
        } else if (s.find(b) == s.end()) {
            printf("ERROR: %d is not found.\n", b);
        } else {
            int ac = find_lca(0, n - 1, a, b);
            if (ac == a) {
                printf("%d is an ancestor of %d.\n", a, b);
            } else if (ac == b) {
                printf("%d is an ancestor of %d.\n", b, a);
            } else {
                printf("LCA of %d and %d is %d.\n", a, b, ac);
            }
        }
    }
    return 0;
}