二叉排序樹

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblem Description

二叉排序樹的定義是：或者是一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分別為二叉排序樹。今天我們要判斷兩序列是否為同一二叉排序樹

Input

開始一個數n，(1<=n<=20)表示有n個需要判斷，n= 0 的時候輸入結束。

接下去一行是一個序列，序列長度小于10，包含(0~9)的數字，沒有重復數字，根據這個序列可以構造出一顆二叉排序樹。

接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉排序樹。(數據保證不會有空樹)

Output

Example Input

2

123456789

987654321

432156789

0

Example Output

NO

NO

Hint

Author

#include<stdio.h>#include<algorithm>#include<string.h>#include<iostream>#include<math.h>#include<queue>#include<stdlib.h>using namespace std;typedef struct node{   char data;   struct node *l;   struct node *r;}tree;char c[1002],d[1002],cc[1002];int k,kk,kkk;void insert(tree*&root,int x){     if(root == NULL)     {        tree*p;        p = (tree*)malloc(sizeof(tree));        p->data = x;        p->l = NULL;        p->r = NULL;        root =  p;     }     else if(x<root->data)     {         insert(root->l,x);     }     else     {        insert(root->r,x);     }}tree* build(tree*root,char a[],int o){    root = NULL;    for(int i= 0;i< o;i++)    {       insert(root,a[i]);    }    return root;}int top;//控制空格輸出void inout(tree*root){     if(root)     {         inout(root->l);         /*if(top)top=0;         else printf(" ");*/         printf("%d",root->data);         inout(root->r);     }}void firstout(tree*root){    if(root)    {       firstout(root->l);       c[k++] = root->data;       firstout(root->r);    }}void lastout(tree*root){    if(root)    {       firstout(root->l);       firstout(root->r);       cc[kkk++] = root->data;    }}void firstout2(tree*root){    if(root)    {       firstout(root->l);       d[kk++] = root->data;       firstout(root->r);    }}void qiangge(tree*root,tree* root2){    if(root&&root2)    {       if(root->data!=root2->data)top = 0;       else       {          qiangge(root->l,root2->l);          qiangge(root->r,root2->r);       }    }    else if(root&&!root2||!root&&root2)top = 0;}int main(){    int n,o,oo;    while(~scanf("%d",&n))    {       if(n==0)       break;       //top = 1;        char a[1002],b[1002],i;        scanf("%s",a);         //k = kkk = 0;         tree *root;         o = strlen(a);         root = build(root,a,o);        // firstout(root);         //lastout(root);         for(i=0;i<n;i++)         {           top = 1;           scanf("%s",b);           //kk=0;           tree*root2;           oo = strlen(b);           root2 = build(root,b,oo);          // firstout2(root2);           qiangge(root,root2);           if(top)printf("YES/n");           else printf("NO/n");           /*if(strcmp(c,d)==0)           printf("YES/n");           else if(strcmp(cc,d)==0)           printf("YES/n");           else if(strcmp(a,b)==0)           printf("YES/n");           else           printf("NO/n");*/         }    }   return 0;}/***************************************************User name: jk160505徐紅博Result: AcceptedTake time: 0msTake Memory: 168KBSubmit time: 2017-02-08 09:53:39****************************************************/