题解 | #二叉搜索树#

二叉树先序和中序序列可唯一确定一颗二叉树。节点元素相同的二叉排序树中序序列必相等，所以需要比较先序序列。

#include <ios>
#include <iostream>
using namespace std;
struct treeNode {
    int data;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(int i) {
        data = i;
        leftChild = NULL;
        rightChild = NULL;
    }
};
treeNode* insert(treeNode* root, int x) {
    if (root == NULL) {
        root = new treeNode(x);
    } else if (root->data > x) {
        root->leftChild = insert(root->leftChild, x);
    } else {
        root->rightChild = insert(root->rightChild, x);
    }
    return root;
}
void preOrder(treeNode* root, string& outStr) {
    if (root == NULL) return;
    outStr += char(root->data + '0');
    preOrder(root->leftChild, outStr);
    preOrder(root->rightChild, outStr);
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        if (n == 0) break;

        string str1;
        cin >> str1;
        treeNode* root1 = NULL;
        string preOrderStr1;//基准二叉树的先序遍历序列

        for (int i = 0; i < str1.size(); i++) {
            root1=insert(root1, str1[i] - '0');
        }
        preOrder(root1, preOrderStr1);
        for (int i = 0; i < n; i++) {
            string str2;
            string preOrderStr2;//其他二叉树的比较序列
            cin >> str2;
            treeNode* root2 = NULL;
            for (int i = 0; i < str2.size(); i++) {
                root2=insert(root2, str2[i] - '0');
            }
            preOrder(root2, preOrderStr2);
            if (preOrderStr2 == preOrderStr1)
                cout << "YES" << endl;
            else cout << "NO" << endl;
        }

    }
}
// 64 位输出请用 printf("%lld")