个人练习-PAT甲级-1143 Lowest Common Ancestor

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805343727501312

题目大意：给出BST的先序遍历，给出两个节点，求这两个节点的最深公共祖先。如果节点不存在或者公共祖先不存在或某一个节点就是祖先，需要特殊输出。

思路：建树，DFS找出从根到U和V的路径path_u和path_v，然后遍历，找到第一个不相同的元素即可。没找到说明就是没有共同祖先。如果path_u是path_v是空的，说明这个元素根本不在树里。

完整代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 


using namespace std;


class Node{
public:
    int val;
    Node* left, *right;

    Node(){left = right = nullptr;}
    Node(int val) { this->val = val; left = right = nullptr;}
};


vector<int> pre;
vector<int> path_u, path_v;
Node* root;


Node* buildTree(int s, int t) {
    if (s > t)
        return nullptr;
    Node* parent = new Node(pre[s]);
    int l = s+1;
    int r = l;
    while (r <= t) {
        if (pre[r] > pre[s])
            break;
        else
            r++;
    }
    parent->left = buildTree(l, r-1);
    parent->right = buildTree(r, t);
    return parent;
}


void getPath(vector<int>& path, Node* parent, int v) {
    if (parent == nullptr)
        return;
    path.push_back(parent->val);
    if (parent->val == v)
        return;
    if (v < parent->val)
        getPath(path, parent->left, v);
    else
        getPath(path, parent->right, v);
}


int main() {
    int M, N;
    scanf("%d %d", &M, &N);
    for (int i = 0; i < N; i++) {
        int tmp;
        scanf("%d", &tmp);
        pre.push_back(tmp);
    }

    root = buildTree(0, N-1);

    for (int i = 0; i < M; i++) {
        int U, V;
        bool flag_u = true, flag_v = true;
        scanf("%d %d", &U, &V);
        path_u.clear();
        path_v.clear();
        getPath(path_u, root, U);
        getPath(path_v, root, V);
        if (path_u.back() != U)
            flag_u = false;
        if (path_v.back() != V)
            flag_v = false;

        if (!flag_u & !flag_v) {
            printf("ERROR: %d and %d are not found.\n", U, V);
            continue;
        }
        if (!flag_u) {
            printf("ERROR: %d is not found.\n", U);
            continue;
        }
        if (!flag_v) {
            printf("ERROR: %d is not found.\n", V);
            continue;
        }

        int len = min(path_u.size(), path_v.size());
        int ptr;
        for (ptr = 0; ptr < len; ptr++) {
            if (path_v[ptr] != path_u[ptr])
                break;
        }
        ptr--;
        int A = path_v[ptr];
        if (U == A) {
            printf("%d is an ancestor of %d.\n", A, V);
            continue;
        }
        if (V == A) {
            printf("%d is an ancestor of %d.\n", A, U);
            continue;
        }
        printf("LCA of %d and %d is %d.\n", U, V, A);
    }

    delete root;

    return 0;
}

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120