Cho trước một dãy số, từ đó xây dựng cây nhị phân tìm kiếm (BST). Sau đó, với nhiều dãy số khác, kiểm tra xem chúng có tạo ra BST giống hệt cây gốc hay không.

Đầu vào

• Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 20), số lượng dãy cần kiểm tra. Nếu n = 0 thì dừng chương trình.
• Dòng tiếp theo là dãy gốc — chuỗi các chữ số từ '0' đến '9', không trùng lặp, độ dài dưới 10 ký tự.
• n dòng sau, mỗi dòng là một dãy số có cùng định dạng với dãy gốc.

Đầu ra

• Với mỗi dãy, in ra YES nếu cây BST được tạo ra giống cây gốc, ngược lại in NO.

Ví dụ

2
567432
543267
576342
0

Kết quả

YES
NO

Giải pháp

Ý tưởng: Hai dãy số tạo ra cùng một BST khi và chỉ khi thứ tự chèn của chúng tạo ra cấu trúc cây giống nhau. Ta có thể so sánh bằng cách duyệt tiền thứ tự (preorder) — vì preorder của BST duy nhất xác định cấu trúc cây nếu không có phần tử trùng lặp.

#include <iostream>
#include <string>
using namespace std;

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

Node* buildTree(const string& seq) {
    Node* root = nullptr;
    for (char c : seq) {
        int num = c - '0';
        Node** curr = &root;
        while (*curr != nullptr) {
            if (num < (*curr)->val)
                curr = &((*curr)->left);
            else
                curr = &((*curr)->right);
        }
        *curr = new Node(num);
    }
    return root;
}

string getPreorder(Node* node) {
    if (!node) return "";
    string left = getPreorder(node->left);
    string right = getPreorder(node->right);
    return to_string(node->val) + left + right;
}

void deleteTree(Node* node) {
    if (!node) return;
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        string base;
        cin >> base;
        Node* refTree = buildTree(base);
        string refPre = getPreorder(refTree);

        for (int i = 0; i < n; ++i) {
            string test;
            cin >> test;
            Node* testTree = buildTree(test);
            string testPre = getPreorder(testTree);
            cout << (refPre == testPre ? "YES" : "NO") << endl;
            deleteTree(testTree);
        }

        deleteTree(refTree);
    }
    return 0;
}