题目描述:
判断两序列是否为同一二叉搜索树序列
Input
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。 接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
Output
如果序列相同则输出YES,否则输出NO
Sample Input
Sample Output
YES
NO
代码
-
#include <iostream>
-
#include <string.h>
-
using namespace std;
-
int main()
-
{
-
char l1[10];
-
int n;
-
int num;
-
int j;
-
int tree[1025];
-
char l2[10];
-
int tree2[1025];
-
int i;
-
while(cin>>n)
-
{
-
if(n==0)
-
break;
-
cin>>l1;
-
memset(tree,-1,sizeof(tree));
-
for(i=0;l1[i];i++)
-
{ //构造二叉搜索树
-
num = l1[i] - '0';
-
j = 1;
-
while(tree[j]!=-1)
-
{
-
if(num <= tree[j])
-
j = j*2;
-
else
-
j = j*2 + 1;
-
}
-
tree[j] = num;
-
}
-
while(n--)
-
{ //输入n个序列
-
cin>>l2;
-
memset(tree2,-1,sizeof(tree2));
-
for(i=0;l2[i];i++)
-
{ //构造比较二叉搜索树
-
num = l2[i] - '0';
-
j = 1;
-
while(tree2[j]!=-1)
-
{
-
if(num <= tree2[j])
-
j = j*2;
-
else
-
j = j*2 + 1;
-
}
-
tree2[j] = num;
-
}
-
-
for(i=0;i<=1024&&tree[i]==tree2[i];i++)
-
; //比较
-
if(i>1024)
-
cout<<"YES"<<endl;
-
else
-
cout<<"NO"<<endl;
-
}
-
}
-
return 0;
-
}
http://blog.csdn.net/sjf0115/article/details/8682973
http://www.cnblogs.com/yym2013/p/3552800.html
http://www.cnblogs.com/yuyixingkong/p/3286077.html
阅读(1239) | 评论(0) | 转发(0) |