題目1009：二叉搜索樹

如果序列相同則輸出YES，否則輸出NO

樣例輸入：

2
567432
543267
576342
0

樣例輸出：

YES
NO

來源：

2010年浙江大學計算機及軟件工程研究生機試真題

AC代碼：

//前序遍歷序列和中序遍歷序列能唯一確定一個二叉樹
//本題關鍵在於數的構建和遍歷

#include
#include
#define N 20

struct Node { //二叉樹節點結構體
	char id;
	Node *lchild;
	Node *rchild;
};

Node *nodes[N];
char bst[N], s[N]; //接受輸入的字符串
char in1[N], pre1[N], in2[N], pre2[N]; //存放構建好的二叉樹的中序和前序遍歷序列
int k; //遍歷增量

void build(Node *no, Node *root) { //二叉樹的構建
	if(no->id > root->id) {
		if(root->rchild==NULL)
			root->rchild = no;
		else
			build(no,root->rchild);
	}
	if(no->id < root->id) {
		if(root->lchild==NULL)
			root->lchild = no;
		else
			build(no,root->lchild);
	}
}

void inOrder(Node *root, char in[]) { //中序遍歷
	if(root->lchild != NULL)
		inOrder(root->lchild,in);
	in[k++] = root->id; //將遍歷結果存放到數組，方便後面的序列比較
	if(root->rchild != NULL)
		inOrder(root->rchild,in);
}

void preOrder(Node *root, char pre[]) { //前序遍歷
	pre[k++] = root->id;
	if(root->lchild != NULL)
		preOrder(root->lchild,pre);	
	if(root->rchild != NULL)
		preOrder(root->rchild,pre);
}

int main() {
	//freopen("in.txt","r",stdin);
	int n, i;
	while(scanf("%d",&n)!=EOF && n) {
		scanf("%s",bst);
		int len = strlen(bst);
		for(i=0; iid = bst[i];
			nodes[i]->lchild = NULL; //節點左右孩子初始化為空
			nodes[i]->rchild = NULL;
		}
		for(i=1; iid = s[i];
				nodes[i]->lchild = NULL;
				nodes[i]->rchild = NULL;
			}
			for(i=1; i