1920 ProblemB二叉検索ツリー
質問B:二叉検索ツリー
時間制限:1 Secメモリ制限:32 MBコミット:52解決:36
タイトルの説明
2つのシーケンスが同じツリーシーケンスであるかどうかを判断
入力
1個数nを開始し、(1<=n<=20)はn個あると判断し、n=0のときに入力が終了することを示す.次の行は1つのシーケンスで、シーケンスの長さは10未満で、(0~9)の数字を含んで、繰り返しの数字がなくて、このシーケンスによって1粒の二叉探索木を構築することができます.次のn行にはn個のシーケンスがあります.各シーケンスのフォーマットは最初のシーケンスと同じです.この2つのシーケンスが同じ二叉検索ツリーを構成できるかどうかを判断してください.
しゅつりょく
シーケンスが同一であればYES、そうでなければNOを出力する
サンプル入力
サンプル出力
経験の総括
まず、最も原始的な二叉ソートツリーを作成し、次に、その先序と中序遍歴のシーケンスを格納し、次のn例は、それぞれ二叉ソートツリーを作成し、先序と中序遍歴を行い、この2つの遍歴のシーケンスが完全に等しい限り、この2つの二叉ソートツリーが完全に同じであることを説明し、出力すればよい.~~( 。ớ ₃ờ)ھ
正しいコード
時間制限:1 Secメモリ制限:32 MBコミット:52解決:36
タイトルの説明
2つのシーケンスが同じツリーシーケンスであるかどうかを判断
入力
1個数nを開始し、(1<=n<=20)はn個あると判断し、n=0のときに入力が終了することを示す.次の行は1つのシーケンスで、シーケンスの長さは10未満で、(0~9)の数字を含んで、繰り返しの数字がなくて、このシーケンスによって1粒の二叉探索木を構築することができます.次のn行にはn個のシーケンスがあります.各シーケンスのフォーマットは最初のシーケンスと同じです.この2つのシーケンスが同じ二叉検索ツリーを構成できるかどうかを判断してください.
しゅつりょく
シーケンスが同一であればYES、そうでなければNOを出力する
サンプル入力
6
45021
12045
54120
45021
45012
21054
50412
0
サンプル出力
NO
NO
YES
NO
NO
NO
経験の総括
まず、最も原始的な二叉ソートツリーを作成し、次に、その先序と中序遍歴のシーケンスを格納し、次のn例は、それぞれ二叉ソートツリーを作成し、先序と中序遍歴を行い、この2つの遍歴のシーケンスが完全に等しい限り、この2つの二叉ソートツリーが完全に同じであることを説明し、出力すればよい.~~( 。ớ ₃ờ)ھ
正しいコード
#include
#include
using namespace std;
struct node
{
int data;
node *lchild;
node *rchild;
};
void insert(node * &root, int x)
{
if(root==NULL)
{
node * temp=new node;
temp->data=x;
temp->rchild=temp->lchild=NULL;
root=temp;
return ;
}
if(x==root->data)
{
return;
}
else if(x>root->data)
{
insert(root->rchild,x);
}
else
{
insert(root->lchild,x);
}
}
void pre(node *root,vector &answer)
{
if(root==NULL)
{
return ;
}
answer.push_back(root->data);
pre(root->lchild,answer);
pre(root->rchild,answer);
}
void in(node *root,vector &answer)
{
if(root==NULL)
{
return ;
}
in(root->lchild,answer);
answer.push_back(root->data);
in(root->rchild,answer);
}
int main()
{
int n,data;
char temp[15];
vector opre,oin,tpre,tin;
while(~scanf("%d",&n))
{
if(n==0)
break;
opre.clear();
oin.clear();
scanf("%s",temp);
int k=0;
while(temp[k]!='\0')
k++;
node * root=NULL;
for(int i=0;i