Kiểm tra mảng có thể biểu diễn BST chiều cao n trong C++

Cho mảng A, kiểm tra xem có thể xây dựng BST có chiều cao n từ mảng này không. Khi chèn vào BST: giá trị > gốc đi phải, < gốc đi trái. Ví dụ mảng {50, 20, 9, 25, 10} không hợp lệ, nhưng {50, 30, 20, 25, 10} hợp lệ.

Cách kiểm tra không cần xây cây: dùng hai biến min = -∞, max = +∞ đánh dấu giới hạn cho cây con trái/phải. Duyệt mảng, cập nhật min/max theo quy tắc BST.

Ví dụ

#include <iostream>
using namespace std;

bool canMakeBSTifHeightN(int arr[], int n) {
    int min = INT_MIN;
    int max = INT_MAX;
    for(int i = 1; i < n; i++){
        if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
            min = arr[i - 1];
        } else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
            max = arr[i - 1];
        } else {
            return true;
        }
    }
    return false;
}

int main() {
    int elements[] = {50, 30, 20, 25, 10};
    int n = sizeof(elements)/sizeof(elements[0]);
    if (canMakeBSTifHeightN(elements, n))
        cout << "We can make BST of height " << n;
    else
        cout << "We can not make BST of height " << n;
}

Kết quả

We can make BST of height 5