Problem Description
判断两序列是否为同一二叉搜索树序列
Input
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
Output
如果序列相同则输出YES,否则输出NO
Sample Input
2 567432 543267 576342 0
Sample Output
YES NO
首道的二叉树,写的不这么好。 凑合着自己以后复习使用吧。
#include <stdio.h> #include <stdlib.h> #include <string.h> int cnt,a[12],b[12]; typedef struct Tree { int num; Tree *Left; Tree *Right; }Tree; Tree *root; Tree *Creat(int value) //建树 { Tree *T = (Tree *)malloc(sizeof(Tree)); T->Left = NULL; T->Right = NULL; T->num = value; return T; } Tree *Insert(Tree *temp,int value) //插入值 { Tree *T; if(temp == NULL){ T = Creat(value); temp = T; }else { if(value <= temp->num) temp->Left = Insert(temp->Left,value); else temp->Right = Insert(temp->Right,value); } return temp; } void save(Tree *root) //根据题目要求而写的函数与二叉树无关 { if(root!=NULL) { b[cnt++] = root->num; save(root->Left); save(root->Right); } } int main() { int T,n,i; char str[10]; while(scanf("%d",&T),T) { scanf("%s",str); cnt = 0; root = NULL; n = strlen(str); for(i = 0;i < n;i++) { int t = str[i] -'0'; root = Insert(root,t); } save(root); for(i = 0;i < n;i++) a[i] = b[i]; while(T--) { scanf("%s",str); cnt = 0; root = NULL; n = strlen(str); for(i = 0;i < n;i++) { int t = str[i] - '0'; root = Insert(root,t); } save(root); for(i = 0;i < n;i++) if(a[i] != b[i]) { puts("NO"); break; } if(i == n) puts("YES"); } } return 0; }