题解 | #二叉搜索树#
二叉搜索树
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这才才好拼接