题目描述
判断两序列是否为同一二叉搜索树序列
输入
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出
如果序列相同则输出YES，否则输出NO
样例输入
6 45021 12045 54120 45021 45012 21054 50412 0
样例输出
NO NO YES NO NO NO
思路：建树判断两个树的前序和中序遍历是否相同
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
struct node{int data;node* lChild;node* rChild;
};
node* Newnode(int x){node* root=new node;root->data=x;root->lChild=root->rChild=NULL;return root;
}void change(char a[],int b[])
{for(int i=0;i<strlen(a);i++){b[i]=a[i]-'0';}
}
void insert(node* &root,int x)
{if(root==NULL){root=Newnode(x); //注意这里是root=Newnode(x);不是单独Newnode(x); return;}if(x==root->data)return;if(x>root->data)insert(root->rChild,x);else{insert(root->lChild,x);}
}
node* create(int data[],int n){int i;node* root=NULL;for(i=0;i<n;i++){insert(root,data[i]);}return root;
}
void preorder(node* root,vector<int> &q)
{if(root==NULL)return;//printf("%d ",root->data);q.push_back(root->data);preorder(root->lChild,q);preorder(root->rChild,q);}
void inorder(node* root,vector<int> &q)
{if(root==NULL)return;inorder(root->lChild,q);//printf("%d ",root->data);q.push_back(root->data);inorder(root->rChild,q);
}
int main(){int n; while(scanf("%d",&n)!=EOF&&n!=0){vector<int> pre1,in1;char a[20];int tr1[20];scanf("%s",a);change(a,tr1);int len1=strlen(a);node* root1=create(tr1,len1);preorder(root1,pre1);inorder(root1,in1);while(n--){char b[20];int tr2[20];scanf("%s",b);change(b,tr2);int len2=strlen(b);node* root2=create(tr2,len2);vector<int>pre2,in2;preorder(root2,pre2);inorder(root2,in2);if(pre2.size()!=pre1.size())printf("NO\n");else {int flag=1;for(int i=0;i<pre1.size();i++){if(pre1[i]!=pre2[i]||in1[i]!=in2[i]){printf("NO\n");flag=0;break;}}if(flag==1)printf("YES\n"); }}}return 0;
}