题解 | 二叉搜索树

一个中序遍历序列+（层序/前序/后序）中任意一个序列可以唯一确定一颗树形。

思路：先建好二叉排序树，再比较前序和中序序列是否都一致。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

typedef struct LNode {
    char data;
    struct LNode* left;
    struct LNode* right;
} TreeNode, *BiTree;
//建二叉排序树
void insertBST(BiTree& root, char data) { //树一定要传入引用数据类型
    //新建一个树结点
    TreeNode* p = new TreeNode;
    p->data = data;
    p->left = NULL;
    p->right = NULL;
    TreeNode* pre = new TreeNode;
    TreeNode* cur = new TreeNode;
    //若此时根为空，则树结点为根
    if (root == NULL) {
        root = p;
    } else {
        cur = root;//当前结点
        while (1) {
            //若此时根不空且data大于根值，找到根右边空的位置插入
            if (data > cur->data) {
                pre = cur;
                cur = cur->right;
                if (cur == NULL) {
                    pre->right = p;
                    break;
                }
            } else {
                //若此时根不空且data小于根值，找到根左边空的位置插入
                pre = cur;
                cur = cur->left;
                if (cur == NULL) {
                    pre->left = p;
                    break;
                }
            }
        }
    }
}
//前序遍历
string preOrder(BiTree root) {
    if (root == NULL)return "";
    return root->data + preOrder(root->left) + preOrder(root->right);
}
//中序遍历
string InOrder(BiTree root) {
    if (root == NULL) return "";
    return InOrder(root->left) + root->data + InOrder(root->right);
}
int main() {
    int N;
    char data;
    BiTree root1 = NULL;//初始化空树
    string str1;
    char arr1[1000];
    while (scanf("%d", &N) != EOF) {
        if (N == 0)break;
        scanf("%s", arr1);
        str1 = arr1;
        for (int i = 0; str1[i] != '\0'; i++) {
            insertBST(root1, str1[i]);//建第一个序列的树
        }
        while (N--) { //输入N个序列
            string str2 = "";
            BiTree root2 = NULL;
            scanf("%s", arr1);
            str2 = arr1;
            //建第N个树
            for (int i = 0; str2[i] != '\0'; i++) {
                insertBST(root2, str2[i]);
            }
            //比较
            if (preOrder(root1) == preOrder(root2) && InOrder(root1) == InOrder(root2)) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }


    return 0;
}