杭电3791 二叉搜索树

二叉搜索树

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1849    Accepted Submission(s): 827

Problem 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

额，最近没什么发文章，其实我都有认真地敲代码的哦。。。

最近在学二叉树，经过几题二叉树的水题（对我来说可不是。。。）的练习（其实一边看题解一边做），我终于对二叉树有一些了解了。。。

这题是典型的水题，了解意思后就容易做了。。

题意以例子来表示吧：567432，root为5，然后6>5放在5的右儿子，7>5，7>6，所以放5的右儿子的右儿子，4<5放5的左儿子，依此类推，构造二叉树。题目要判断后面的二叉树和第一棵是不是同一棵树。

看了题解。。。

据说只有前（后）序和中序都相同才能算同一棵树，于是我写了两种排序来判断。

后来我看到资料说二叉树不仅能用链表来表示，还能用数组表示，于是我考虑下有时间写个用数组来判断的程序，貌似能会容易多了。。。

不过现在贴出来的是链表的，代码真的很难看。。。

AC代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAXN 30

int TOrder[MAXN], cnt = 0;

typedef struct Tree
{
	int value;
	struct Tree *l, *r;
} tree;

tree* root;

tree* newnode(int val)
{
	tree* u = (tree*) malloc(sizeof(tree));
	if (u != NULL)
	{
		u->value = val;
		u->l = u->r = NULL;
	}
	return u;
}

tree* addnode(tree *node, int val)
{
	if (node == NULL)
		node = newnode(val);
	else
	{
		if(val >= node->value)
			node->l = addnode(node->l, val);
		else
			node->r = addnode(node->r, val);
	}
	return node;
}

void Inorder(tree* root)
{
	if (root != NULL)
	{
		Inorder(root->l);
		TOrder[cnt++] = root->value;
		Inorder(root->r);
	}
}

void Preorder(tree* root)
{
	if (root != NULL)
	{
		TOrder[cnt++] = root->value;
		Preorder(root->l);
		Preorder(root->r);
	}
}

int main()
{
	int n;
	while ((scanf("%d", &n) != EOF) && n)
	{
		root = NULL;
		cnt = 0;
		char bef[MAXN] = {0};
		scanf("%s", bef);
		for (int i = 0; i < strlen(bef); i++)
			root = addnode(root, bef[i] - '0');
		int BefIn[MAXN] = {0}, BefPre[MAXN] = {0};
		memset (TOrder, 0, sizeof(TOrder));
		Inorder(root);
		while (cnt--)
			BefIn[cnt] = TOrder[cnt];
		cnt = 0;
		memset (TOrder, 0, sizeof(TOrder));
		Preorder(root);
		while (cnt--)
			BefPre[cnt] = TOrder[cnt];
		while(n--)
		{
			char aft[MAXN] = {0};
			scanf("%s", aft);
			root = NULL;
			for (int i = 0; i < strlen(bef); i++)
				root = addnode(root, aft[i] - '0');
			int AftIn[MAXN] = {0}, AftPre[MAXN] = {0};
			cnt = 0;
			memset (TOrder, 0, sizeof(TOrder));
			Inorder(root);
			while (cnt--)
				AftIn[cnt] = TOrder[cnt];
			cnt = 0;
			memset (TOrder, 0, sizeof(TOrder));
			Preorder(root);
			while (cnt--)
				AftPre[cnt] = TOrder[cnt];
			bool ok = 1;
			for (int i = 0; i < strlen(bef) && ok; i++)
				if (BefIn[i] != AftIn[i] || BefPre[i] != AftPre[i])
					ok = 0;
			if (ok)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
	return 0;
}