题解 | #二叉搜索树#

暴力方法，先序与中序均相同则是长得一样的二叉树

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>

using namespace std;

class Treenode{
public:
	char data;
	Treenode* lchild;
	Treenode* rchild;
	Treenode(char x):data(x),lchild(NULL),rchild(NULL){}
};

Treenode* Build(Treenode* T, char x){
	if(!T){
		return new Treenode(x);
	}else{
		if(x < T->data){
			T->lchild = Build(T->lchild, x);
		}else if(x > T->data){
			T->rchild = Build(T->rchild, x);
		}
	}
	return T;
}

void Preorder(Treenode* T, string &s){
	if(!T){
		return;
	}
	s.push_back(T->data);
	Preorder(T->lchild, s);
	Preorder(T->rchild, s);
}

void Inorder(Treenode* T, string &s){
	if(!T){
		return;
	}
	Inorder(T->lchild, s);
	s.push_back(T->data);
	Inorder(T->rchild, s);
}

bool judge(Treenode* T,Treenode* T1){
	string s1, s2, s3, s4;
	Preorder(T, s1);
	Inorder(T, s2);
	Preorder(T1, s3);
	Inorder(T1, s4);
	if(s1==s3 && s2==s4){
		return true;
	}else{
		return false;
	}
}

int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		getchar();
		Treenode* T;
		Treenode* t[n];
		T = NULL;
		for(int i=0; i<n; i++){
			t[i] = NULL;
		}
		string s;
		getline(cin, s);
		for(int i=0; i<s.size(); i++){
			T = Build(T, s[i]);
		}
		for(int j=0; j<n; j++){
			getline(cin, s);
			for(int i=0; i<s.size(); i++){
				t[j] = Build(t[j], s[i]);
			}
			if(judge(T,t[j])){
				printf("YES\n");
			}else{
				printf("NO\n");
			}
		}
	}
	return 0;
}