Description:

判断两序列是否为同一二叉搜索树序列

Input:

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

Output:

如果序列相同则输出YES，否则输出NO

Sample Input:

2
567432
543267
576342
0

Sample Output:

YES
NO

题目链接

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

——百度百科

按照二叉搜索树的要求建树后进行对比判断即可。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

struct tree {
	int data;
	tree *LeftChild, *RightChild;
	tree(): data(INF), LeftChild(NULL), RightChild(NULL) {}
};

bool flag;
tree *standardroot;
tree *judgeroot;

void addvertex(tree *u, int data) {
	if (u -> data == INF) {
		u -> data = data;
		return;
	}
	if (data < u -> data) {
		if (u -> LeftChild == NULL) {
			u -> LeftChild = new tree;
		}
		addvertex(u -> LeftChild, data);
	}
	else if(data > u -> data) {
		if (u -> RightChild == NULL) {
			u -> RightChild = new tree;
		}
		addvertex(u -> RightChild, data);
	}
}

void check(tree *f, tree *g) {
	if (f -> data != g -> data) {
		flag = 0;
		return;
	}
	if (f -> LeftChild && g -> LeftChild) {
		check(f -> LeftChild, g -> LeftChild);
	}
	else if ((f -> LeftChild == NULL && g -> LeftChild) || (f -> LeftChild && g -> LeftChild)) {
		flag = 0;
	}
	if (!flag) {
		return;
	}
	if (f -> RightChild && g -> RightChild) {
		check(f -> RightChild, g -> RightChild);
	}
	else if ((f -> RightChild == NULL && g -> RightChild) || (f -> RightChild && g -> RightChild)) {
		flag = 0;
	}
}

void remove(tree *u) {
	if (u == NULL) {
		return;
	}
	remove(u -> LeftChild);
	remove(u -> RightChild);
	delete u;
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	while (~scanf("%d", &n)) {
		standardroot = new tree;
		string standard;
		cin >> standard;
		for (int i = 0; i < int(standard.size()); ++i) {
			addvertex(standardroot, int(standard[i] - '0'));
		}
		while (n--) {
			string judge;
			cin >> judge;
			judgeroot = new tree;
			for (int i = 0; i < int(judge.size()); ++i) {
				addvertex(judgeroot, int(judge[i] - '0'));
			}
			flag = 1;
			check(standardroot, judgeroot);
			if (flag) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
			remove(judgeroot);
		}
		remove(standardroot);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}