题解 | #二叉搜索树#

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

struct treenode {
	char data;
	treenode *lchild;
	treenode *rchild;
};

void insert(treenode *&root, int data) {
	treenode *pnewnode = new treenode;
	pnewnode->data = data;
	pnewnode->lchild = NULL;
	pnewnode->rchild = NULL;
	if (root == NULL) {
		root = pnewnode;
	} else {
		treenode *pre = root;
		treenode *pcur;
		while (true) {
			if (data < pre->data) {
				pcur = pre->lchild;
				if (pcur == NULL) {
					pre->lchild = pnewnode;
					break;
				} else {
					pre = pcur;
				}
			} else {
				pcur = pre->rchild;
				if (pcur == NULL) {
					pre->rchild = pnewnode;
					break;
				} else {
					pre = pcur;
				}
			}
		}
	}
}

string inorder(treenode *root) {
	if (root == NULL) {
		return "";
	} else {
		return inorder(root->lchild) + root->data + inorder(root->rchild);
	}
}

string preorder(treenode *root) {
	if (root == NULL) {
		return "";

	}
	return root->data + preorder(root->lchild) + preorder(root->rchild);
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			break;
		}
		char str1[100];
		scanf("%s", str1);
		treenode *root1 = NULL;
		for (int i = 0; str1[i] != '\0'; ++i) {
			insert(root1, str1[i]);
		}
		string pre1 = preorder(root1);
		string in1 = inorder(root1);
		char str2[100];
		for (int i = 0; i < n; ++i) {
			scanf("%s", str2);
			treenode *root2 = NULL;
			for (int i = 0; str2[i] != '\0'; ++i) {
				insert(root2, str2[i]);
			}
			string pre2 = preorder(root2);
			string in2 = inorder(root2);
			if (pre1 == pre2 && in1 == in2) {
				printf("YES\n");
			} else {
				printf("NO\n");
			}
		}
	}
}