Kiểm tra mảng có phải preorder của BST C++

Cho mảng, kiểm tra có phải thứ tự preorder (NLR) của một BST không.

Ví dụ: {40, 30, 35, 80, 100} → YES (cây BST hợp lệ).

Giải thuật (Stack)

1. Khởi tạo stack rỗng, root = -∞
2. Duyệt mảng preorder: - Nếu phần tử < root → false (vi phạm BST) - Pop stack khi phần tử > stack.top(), cập nhật root = phần tử vừa pop - Push phần tử vào stack
3. Duyệt hết → true

Ví dụ minh họa

#include <iostream>
#include <stack>
#include <climits>
using namespace std;

bool isValidPreorder(int pre[], int n) {
    stack<int> stk;
    int root = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        if (pre[i] < root) return false;
        while (!stk.empty() && stk.top() < pre[i]) {
            root = stk.top();
            stk.pop();
        }
        stk.push(pre[i]);
    }
    return true;
}

int main() {
    int pre[] = {40, 30, 35, 80, 100};
    int n = sizeof(pre)/sizeof(pre[0]);
    cout << (isValidPreorder(pre, n) ? "Co the tao BST" : "KHONG the tao BST");
}

Kết quả

Co the tao BST