题解 | #二叉搜索树#

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

typedef char ElementType;

struct TreeNode {
    ElementType data;
    TreeNode* leftChild;
    TreeNode* rightChild;

    TreeNode(ElementType c) {
        this->data = c;
        this->leftChild = nullptr;
        this->rightChild = nullptr;
    }
};

TreeNode* insert(TreeNode* root, ElementType x);

void preOrder(TreeNode* root, string& order);

/**
 * 二叉搜索树--浙江大学
 * @return
 */
int main() {
    int n;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        string sequence;
        cin >> sequence;
        TreeNode* root = nullptr;
        for (int i = 0; i < sequence.size(); ++i) {
            root = insert(root, sequence[i]);
        }
        string order = "";
        preOrder(root, order);
        for (int j = 0; j < n; ++j) {
            string str;
            cin >> str;
            TreeNode* temp = nullptr;
            for (int i = 0; i < str.size(); ++i) {
                temp = insert(temp, str[i]);
            }
            string tmpOrder = "";
            preOrder(temp, tmpOrder);
            if (order == tmpOrder) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}

TreeNode* insert(TreeNode* root, ElementType x) {
    if (root == nullptr) {
        /*
         * 创建新结点
         */
        root = new TreeNode(x);
    } else if (x < root->data) {
        /*
         * 插入到左子树
         */
        root->leftChild = insert(root->leftChild, x);
    } else if (x > root->data) {
        /*
         * 插入到右子树
         */
        root->rightChild = insert(root->rightChild, x);
    } else {
        /*
         * 题目说重复的元素无需输出，因此重复元素我们不进行插入
         */
    }
    return root;
}

void preOrder(TreeNode* root, string& order) {
    if (root == nullptr) {
        return;
    }
    /*
     * 根、左子树、右子树
     */
    order += root->data;
    preOrder(root->leftChild, order);
    preOrder(root->rightChild, order);
}