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を出力する
サンプル入力
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