题解 | #二叉搜索树#

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct BTnode {
    char data;
    struct BTnode* lchild;
    struct BTnode* rchild;

} BTnode, *BTree;

void insert(BTree& T, char c) {
    if (T == NULL) {
        T = (BTree)malloc(sizeof(BTnode));
        T->data = c;
        T->lchild = NULL;
        T->rchild = NULL;
        return ;
    }
    if (c < T->data) {
        insert(T->lchild, c);
    } else
        insert(T->rchild, c);
}
void inorder(BTree T, string& inO) {
    if (T == NULL) return;
    inorder(T->lchild, inO);
    inO += T->data;
    inorder(T->rchild, inO);


}
void preorder(BTree T, string& inO) {
    if (T == NULL) return;
    inO += T->data;
    preorder(T->lchild, inO);
    preorder(T->rchild, inO);
}



int main() {
    int n;
    cin >> n;
    string str;
    cin >> str;
    BTree T = NULL;
    for (int i = 0; i < str.size(); i++) {
        insert(T, str[i]);
    }
    string inO, preO;
    preorder(T, preO);
    inorder(T, inO);

    while (n--) {
        string match;
        cin >> match;
        BTree M = NULL;
        for (int i = 0; i < match.size(); i++) {
            insert(M, match[i]);
        }
        string i, p;
        preorder(M, p);
        inorder(M, i);
        if (p == preO && i == inO) cout << "YES" << endl;
        else cout << "NO" << endl;
    }



}

如果 两颗 树 的前序 中序 全部相同

那么这两颗 二叉树就 一模一样