SDUTOJ 2482 二叉排序樹：構建並比較前序/後序遍歷判斷同構

SDUTOJ 2482 二叉排序樹：構建並比較前序/後序遍歷判斷同構

題目大意

給定字串構建二叉排序樹（BST）。輸入 n 個查詢字串，判斷每個字串構建的 BST 是否與原樹同構（前序或後序遍歷相同即可）。n=0 結束。

解法

1. 插入構建 BST：小於走左，大於等於走右
2. 前序遍歷（根左右）、後序遍歷（左右根）生成字串
3. 查詢字串若與原字串、前序串、後序串任一相同 → YES，否則 NO

代碼實現

#include 
#include 
using namespace std;

struct Node {
    char data;
    Node *l, *r;
    Node(char c) : data(c), l(nullptr), r(nullptr) {}
};

void insert(Node* &root, char key) {
    if (!root) { root = new Node(key); return; }
    if (key < root->data) insert(root->l, key);
    else insert(root->r, key);
}

void preorder(Node* root, string& s) {
    if (!root) return;
    s += root->data;
    preorder(root->l, s);
    preorder(root->r, s);
}

void postorder(Node* root, string& s) {
    if (!root) return;
    postorder(root->l, s);
    postorder(root->r, s);
    s += root->data;
}

int main() {
    int n;
    while (cin >> n && n) {
        string orig; cin >> orig;
        Node* root = nullptr;
        for (char c : orig) insert(root, c);
        string pre, post;
        preorder(root, pre);
        postorder(root, post);
        while (n--) {
            string q; cin >> q;
            if (q == orig || q == pre || q == post) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}

關鍵點

• BST 插入規則固定 → 相同字串必得相同樹
• 前序/後序遍歷唯一確定 BST 結構（中序為排序序列不提供結構信息）
• 字串長度 ≤100，遞歸深度安全
• 內存洩漏在競賽中可忽略，工程代碼需釋放

此題考察 BST 構建與遍歷，邏輯直觀易實現。