Hướng giải của Kiểm tra BST hợp lệ

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Để kiểm tra một cây nhị phân có phải BST hợp lệ hay không, ta sử dụng phương pháp duyệt có giới hạn giá trị cho phép (min-max).

Các bước thực hiện:

  1. Xây dựng cây từ dữ liệu đầu vào (lưu ý xác định nút gốc).
  2. Duyệt cây theo chiều sâu, với mỗi nút:
    • Giá trị của nút phải nằm trong khoảng \((min\_val, max\_val)\).
    • Cây con trái: cập nhật \(max\_val = giá\_trị\_nút\).
    • Cây con phải: cập nhật \(min\_val = giá\_trị\_nút\).
  3. Nếu mọi nút đều thoả mãn, in \(YES\), ngược lại in \(NO\).

Độ phức tạp: \(O(N)\).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

bool isBST(Node* root, long long minVal, long long maxVal) {
    if (!root) return true;
    if (root->val <= minVal || root->val >= maxVal) return false;
    return isBST(root->left, minVal, root->val) && isBST(root->right, root->val, maxVal);
}

int main() {
    int N;
    cin >> N;
    vector<Node*> nodes(N);
    vector<int> val(N);
    for (int i = 0; i < N; ++i) {
        cin >> val[i];
        nodes[i] = new Node(val[i]);
    }
    vector<bool> hasPar(N, false);
    for (int i = 0; i < N - 1; ++i) {
        int u, v; char c;
        cin >> u >> v >> c;
        --u; --v;
        hasPar[v] = true;
        if (c == 'L') nodes[u]->left = nodes[v];
        else nodes[u]->right = nodes[v];
    }
    int rootIdx = -1;
    for (int i = 0; i < N; ++i) if (!hasPar[i]) rootIdx = i;
    cout << (isBST(nodes[rootIdx], LLONG_MIN, LLONG_MAX) ? "YES" : "NO") << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.