题解 | #二叉搜索树#重要模板#

本题思路是在于，根据给定的序列先插入一棵二叉搜索树，随后的序列中，如果有序列的先序和中序序列与其完全一致，则证明后续建树的二叉搜索树和自己一致。需要三个函数：1.建树函数，参数为当前根节点和将要插入的数值2.中序遍历函数，参数为根节点的指针，返回字符串3.先序遍历函数，参数为根节点的指针，返回字符串

注意！！！建树函数的参数根节点需要用引用符号，因为会直接修改原root的值作为下一个参数传入，不然BST树会一直为空

/*判断两序列是否为同一二叉搜索树序列
输入描述：
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字
根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出描述：
如果序列相同则输出YES，否则输出NO*/
#include <bits/stdc++.h>

using namespace std;
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
};

string Preorder(TreeNode* proot) {
    if (proot == nullptr) {
        return "";
    } else {
        return proot->val + Preorder(proot->left) + Preorder(proot->right);
    }
}

string Inorder(TreeNode* proot) {
    if (proot == nullptr) {
        return "";
    } else {
        return Inorder(proot->left) + proot->val + Inorder(proot->right);
    }
}

void insertBST(TreeNode* &proot,
               int data) { //标准的BST建树过程，先new一个节点
    TreeNode* pNew = new TreeNode;
    pNew->val = data;
    pNew->left = nullptr;
    pNew->right =
        nullptr;//每次递归之前新建一个节点，只有值没有左右孩子
    if (proot == nullptr) {//判断是否跳出循环
        proot = pNew;
        //printf("-1\n");
    } else {
        TreeNode* pCur = proot; //向下探索的指针
        TreeNode* pPre; //指向pCur的父亲节点
        while (true) { //向下循环遍历直到找到某节点的左（小于）或右（大于）为空，可以进行new节点的插入
            if (pCur->val < data) {
                pPre = pCur;
                pCur = pCur->right;
                if (pCur == nullptr) {
                    pPre->right = pNew;
                    //printf("%d",pPre->val);
                    break;
                }
            } else {
                pPre = pCur;
                pCur = pCur->left;
                if (pCur == nullptr) {
                    pPre->left = pNew;
                    //printf("%d",pPre->val);
                    break;
                }
            }
        }
    }
}


int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        char strarr[20] = {0};
        scanf("%s", strarr);
        TreeNode* proot1 = nullptr;
        for (int i = 0; strarr[i] != '\0'; i++) {
            insertBST(proot1, strarr[i]);
        }
        string prestr1 = Preorder(proot1);
        string instr1 = Inorder(proot1);
        strarr[20] = {0};

        for (int i = 0; i < n; i++) {
            scanf("%s", strarr);
            TreeNode* proot2 = nullptr;
            for (int j = 0; strarr[j] != '\0'; j++) {
                insertBST(proot2, strarr[j]);
            }
            string prestr2 = Preorder(proot2);
            string instr2 = Inorder(proot2);
            if (prestr1 == prestr2 && instr1 == instr2) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }
}