Verify Preorder Sequence in BST - Kiểm tra preorder BST hợp lệ

Cho dãy số, kiểm tra có phải preorder traversal của BST không (các số duy nhất).

Ví dụ: [5,2,1,3,6] → true.

Giải thuật (Giả lập stack với mảng)

Duyệt preorder, giữ low (giá trị nhỏ nhất cho phép). Dùng biến itr mô phỏng stack. Khi gặp giá trị > stack top, pop và cập nhật low. Nếu giá trị < low → sai.

Cài đặt C++

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

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int itr = -1;
        int low = INT_MIN;
        for (int x : preorder) {
            if (x < low) return false;
            while (itr >= 0 && preorder[itr] < x) {
                low = preorder[itr];
                itr--;
            }
            preorder[++itr] = x;
        }
        return true;
    }
};

int main() {
    Solution ob;
    vector<int> v = {5,2,1,3,6};
    cout << ob.verifyPreorder(v);
    return 0;
}

Đầu vào

{5,2,1,3,6}

Đầu ra

1