题解 | #二叉搜索树#

//土尔逊Torson 编写于2023/06/10
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>

using namespace std;

struct TreeNode10701 {
	char data;
	TreeNode10701 * leftChild;
	TreeNode10701 * rightChild;
};

void insertBST10701(TreeNode10701 *&root, char data) {
	TreeNode10701 *pNewNode = new TreeNode10701;
	pNewNode->data = data;
	pNewNode->leftChild = NULL;
	pNewNode->rightChild = NULL;
	if (root == NULL) {
		root = pNewNode;
	}
	else {
		TreeNode10701 *pPre = root;
		TreeNode10701 *pCur;
		while (true) {
			if (data < pPre->data) {
				pCur = pPre->leftChild;
				if (pCur == NULL) {
					pPre->leftChild = pNewNode;
					break;
				}
				else {
					pPre = pCur;
				}
			}
			else {
				pCur = pPre->rightChild;
				if (pCur == NULL) {
					pPre->rightChild = pNewNode;
					break;
				}
				else {
					pPre = pCur;
				}
			}
		}
	}
}

string InOrder10701(TreeNode10701 *root) {
	if (root == NULL) {
		return "";
	}
	return InOrder10701(root->leftChild) + root->data + InOrder10701(root->rightChild);
}

string PreOrder10701(TreeNode10701 *root) {
	if (root == NULL) {
		return "";
	}
	return root->data + PreOrder10701(root->leftChild) + PreOrder10701(root->rightChild);
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			break;
		}
		char str1[100];
		scanf("%s", str1);
		TreeNode10701 *root1 = NULL;
		for (int i = 0; str1[i] != '\0'; ++i) {
			insertBST10701(root1, str1[i]);
		}
		string preOrder1 = PreOrder10701(root1);
		string inOrder1 = InOrder10701(root1);

		char str2[100];
		for (int idx = 0; idx < n; ++idx) {
			scanf("%s", str2);
			TreeNode10701 *root2 = NULL;
			for (int i = 0; str2[i] != '\0'; ++i) {
				insertBST10701(root2, str2[i]);
			}
			string preOrder2 = PreOrder10701(root2);
			string inOrder2 = InOrder10701(root2);
			if (preOrder1 == preOrder2 && inOrder1 == inOrder2) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
		}
	}
}
// 64 位输出请用 printf("%lld")