题解 | #二叉搜索树#

#include <iostream>
#include <string>
using namespace std;

struct TreeNode {
    char data; //这里为什么要设置成char呢 -> 为了在遍历中能进行拼接
    TreeNode* leftChild;
    TreeNode* rightChild;
};

/**
 * 先序遍历
 * @param root
 * @return 返回先序遍历的字符串
 */
string PreOrder(TreeNode* root) {
    if (root == NULL) {
        return "";
    }
    return root->data + PreOrder(root->leftChild) +  PreOrder(root->rightChild);
}

/**
 * 中序遍历
 * @param root
 * @return 返回中序遍历的字符串
 */
string InOrder(TreeNode* root) {
    if (root == NULL) {
        return "";
    }
    return InOrder(root->leftChild) + root->data + InOrder(root->rightChild);
}

/**
 * 二叉搜索树的插入
 * @param root 根结点
 * @param data 数据
 */
void insertBST(TreeNode*& root, char data) {
    TreeNode* treeNode = new TreeNode;
    treeNode->data = data;
    treeNode->rightChild = NULL;
    treeNode->leftChild = NULL;
    if (root == NULL) { //初始树为空
        root = treeNode;
    } else { //往左边或者右边搜索
        TreeNode* curNode = root;
        TreeNode* preNode = root;
        while (true) {
            int curData = curNode->data;
            if (curData > data) { //往左走
                curNode = preNode->leftChild;
                if (curNode == NULL) { //走到最底部了
                    preNode->leftChild = treeNode;
                    break;
                } else { //继续往下走
                    preNode = curNode;
                }
            } else { //往右走
                curNode = preNode->rightChild;
                if (curNode == NULL) { //走到最底部了
                    preNode->rightChild = treeNode;
                    break;
                } else { //继续往下走
                    preNode = curNode;
                }
            }
        }
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        char seq[20];
        if (n == 0) { //输入0则退出
            break;
        }
        scanf("%s", seq); //输入初始树
        TreeNode* root1 = NULL;
        for (int i = 0; seq[i] != '\0'; i++) {
            insertBST(root1, seq[i]);
        }
        string inOrder1 = InOrder(root1);
        string preOrder1 = PreOrder(root1);
	  
        char str2[100];
        for (int i = 0; i < n; i++) {
            scanf("%s", str2);
            TreeNode* root2 = NULL;
            for (int j = 0; str2[j] != '\0'; j++) {
                insertBST(root2, str2[j]);
            }
            string preOrder2 = PreOrder(root2);
            string inOrder2 = InOrder(root2);
            if (inOrder1 == inOrder2 && preOrder1 == preOrder2) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }
}

初始化root的时候一定要赋值为空！！！！！不然都不知道错在哪里，运行也不会出错。

这题的关键思路就是判断两个树的先序+中序是否相同，相同则是同一棵树

数的data要设置成data这才才好拼接