题解 | 二叉搜索树 中序+先序/后序 唯一 确定一棵树

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

// 无需parent找父节点
struct TreeNode {
	char data;
	TreeNode* left;
	TreeNode* right;
};

// 创建二叉搜索/排序树
void InsertBST(TreeNode* &proot, char data) {
	TreeNode* pNew = new TreeNode;
	pNew->data = data;
	pNew->left = NULL;  // 叶子/新节点 左右指针默认为空
	pNew->right = NULL;

	if (proot == NULL) {
		proot = pNew;  // 新根结点
	}
	else {
		TreeNode* pCur = proot;  // pCur 向下探索
		TreeNode* pPre; // pPre指向pCur的父亲
		while (1) {
			if (pCur->data > data) {
				pPre = pCur;
				pCur = pCur->left;  // 指针往左走，左边小
				if (pCur == NULL) {  // 空结点
					pPre->left = pNew; // 新节点挂在父节点左边
					break;
				}
			}
			else {
				pPre = pCur;
				pCur = pCur->right;  // 指针往右走，右边大
				if (pCur == NULL) {  // 空结点
					pPre->right = pNew;   // 新节点挂在父节点右边
					break;
				}
			}
		}

	}

}

// 获取先序遍历 字符串表示
string PreOrder(TreeNode* proot) {
	if (proot == NULL) {  // 叶子节点下面
 		return "";  // 空串
	}
	// 自动连接字符串
	return proot->data + PreOrder(proot->left) + PreOrder(proot->right);
	// 这个是错误的，str会重复生成，最后只返回第一个栈帧的str
	//string str;
	//if (proot == NULL) {
	//	return "";  // 为空
	//}
	//str.push_back(proot->data + '0');  // + '0' int -> char
	//PreOrder(proot->left);
	//PreOrder(proot->right);
	//return str;
}

// 获取中序遍历 字符串表示
string InOrder(TreeNode* proot) {
	if (proot == NULL) {
		return ""; 
	}
	return  InOrder(proot->left) + proot->data + InOrder(proot->right);
}

// 非平衡二叉树。就是简单的二叉排序树，结点的高度没限制
int main() {
	int n;
	while (scanf("%d", &n) != EOF) {  // 先进入循环，再在里面找退出条件
		if ( n == 0 ) {
			break;  // 退出循环条件
		}
		char strArr[20] = { 0 };
		scanf("%s", strArr);
		TreeNode* proot1 = NULL;
		for (int i = 0; strArr[i] != '\0'; i++) {
			// - '0' char -> int
			//InsertBST(proot1, strArr[i] - '0');  // str[i] - '0' 数字字符转化为数字 
			InsertBST(proot1, strArr[i]);   // 字符 
		}
		string preOrder1 = PreOrder(proot1);
		string inOrder1 = InOrder(proot1);
		
		for (int i = 0; i < n;i++) {
			scanf("%s", strArr);  // 遍历序列长度相同
			TreeNode* proot2 = NULL;
			for (int j = 0; strArr[j] != '\0'; j++) {
				InsertBST(proot2, strArr[j]);   // 字符 
			}
			string preOrder2 = PreOrder(proot2);
			string inOrder2 = InOrder(proot2);
			
			// 字符串支持直接判断等于操作
			if (preOrder2 == preOrder1 && inOrder2 == inOrder1) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}

			/*if(preOrder1.find(preOrder2)!= -1 && inOrder1.find(inOrder2) != -1){
				printf("YES\n");
			}else{
				printf("NO\n");
			}*/
		}

		return 0;
	}
	
}