题解 | #二叉搜索树#

二叉搜索树

https://www.nowcoder.com/practice/3d6dd9a58d5246f29f71683346bb8f1b

#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这才才好拼接

全部评论

相关推荐

最近和朋友聊天,她说了句让我震惊的话:"我发现我连周末点外卖都开始'最优解'了,一定要赶在高峰期前下单,不然就觉得自己亏了。"这不就是典型的"班味入侵"吗?工作思维已经渗透到生活的方方面面。
小型域名服务器:啊?我一直都这样啊?我还以为是我爱贪小便宜呢?每次去实验室都得接一杯免费的开水回去,出门都得规划一下最短路径,在宿舍就吃南边的食堂,在实验室就吃北边的食堂,快递只有顺路的时候才取。
点赞 评论 收藏
分享
小谷围鸡肉卷阿姨:+1,腾子投完一动不动
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务