1499 - 二叉搜索树

判断两序列是否为同一二叉搜索树序列

Input

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。

接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

Output

如果序列相同则输出YES，否则输出NO

Examples

Input

Output

NO
NO
YES
NO
NO
NO

Solution C

#include <stdio.h>
#include <string.h>
int sort(char str[])
{
  int set[11];
  for(int i=0;i<11;i++)
    set[i]=0;
  char qe[11];
  int first=0,rear=0;
  qe[rear++]=str[0];
  set[str[0]-'0']=1;
  while(first!=rear)
  {
    char ch=qe[first++];
    for(int i=0;i<strlen(str);i++)
    {
      if(ch>str[i]&&set[str[i]-'0']==0)
      {
        set[str[i]-'0']=1;
        qe[rear++]=str[i];
        break;
      }
    }
    for(int i=0;i<strlen(str);i++)
    {
      if(ch<str[i]&&set[str[i]-'0']==0)
      {
        set[str[i]-'0']=1;
        qe[rear++]=str[i];
        break;
      }
    }
  }
  for(int i=0;i<strlen(str);i++)
  {
    str[i]=qe[i];
  }
  return 0;
  
}
int main()
{
  while(1)
  {
    int n;
    char std[11];
    char in[11];
    
    scanf("%d",&n);
    if(n==0)
    {
      break;
    }
    scanf("%s",std);
    sort(std);
    for(int i=0;i<n;i++)
    {
      scanf("%s",in);
      sort(in);
      if(strcmp(in,std)==0)
      {
        printf("YES\n");
      }
      else
      {
        printf("NO\n");
      }
    }
  }
  return 1;
}

Solution C++

#include<iostream>
#include<string>
using namespace std;

 

//递归判断是否是同一棵二叉搜索树

//时间复杂度O(nlogn)

bool is_same(string a,string b)
{
         if(a==b)
            return true;
         if(a[0]!=b[0])
            return false;
         string a1,a2,b1,b2;
         unsigned i;
         for(i=1;i<a.size();i++)
         {
             if(a[i]>a[0])
                 a2+=a[i];
             else
                 a1+=a[i];
            if(b[i]>b[0])
                 b2+=b[i];
            else
                  b1+=b[i];
        }

 if(is_same(a1,b1)&&is_same(a2,b2))
        return true;
 else
        return false;
}

int main()
{
        int m;
       string a,b;
       while(1)
       {
             cin>>m;
            if(m==0)
               break;
           cin>>a;
           for(int j=0;j<m;j++)
          {
                cin>>b;
                if(is_same(a,b))
                     cout<<"YES"<<endl;
                else
                     cout<<"NO"<<endl;
            }
  }
 return 0;
}

Time Limit	1 second
Memory Limit	32 MB

Discuss Stats

上一题下一题