글 읽기 - 1991 트리 순회 질문합니다

jh1125kr 8년 전 0

배열(2^26)개 선언하여

각각 배열에 넣어서 트리 순회하는 방식으로 풀었는데

자꾸 틀리네요 ㅠㅠ

if(tmp==j)
{
k=j=j*2;
tmp=0;
}

부분은 tree인덱스가 2면 j=2로 2번반복, 4면 j=4로 4번반복할 수 있게하여

시간 초과 나지않게 설정해준 것 입니다.

#include <iostream>

using namespace std;

char tree[67108864];
int treeSize;
void preOrder(int node)
{
	if(node>treeSize)
		return;
	if(tree[node]!=0)
	{
		cout<<tree[node];
		preOrder(node+node);
		preOrder(node+node+1);
	}
}
void inOrder(int node)
{
	if(node>treeSize)
		return;
	if(tree[node]!=0)
	{
		inOrder(node+node);
		cout<<tree[node];
		inOrder(node+node+1);
	}
}
void postOrder(int node)
{
	if(node>treeSize)
		return;
	if(tree[node]!=0)
	{
		postOrder(node+node);
		postOrder(node+node+1);
		cout<<tree[node];
	}
}
int main()
{
	int N=0, tmp=0, j=2, k=2;
	char a,b,c;
	cin>>N;
	cin>>a>>b>>c;
	if(a=='A'&&b=='B'&&c=='C'){
		tree[1]='A'; tree[2]='B'; tree[3]='C';treeSize=3;}
	else if(a=='A'&&b=='B'&&c=='.'){
		tree[1]='A'; tree[2]='B'; treeSize=2;} 
	else if(a=='A'&&b=='.'&&c=='.'){
		tree[1]='A';treeSize=1;}
	else if(a=='A'&&b=='.'&&c=='B'){
		tree[1]='A'; tree[3]='B'; treeSize=3;}

	for(int i=2; i<=N; i++)
	{
		cin>>a>>b>>c;
		if(tmp==j)
		{
			k=j=j*2;
			tmp=0;
		}
		while(1)
		{
			if(tree[j]==a&&b!='.'&&c!='.')
			{
				tree[j*2]=b;
				tree[j*2+1]=c;
				treeSize=j*2+1;
				break;
			}
			else if(tree[j]==a&&b!='.'&&c=='.')
			{
				tree[j*2]=b;
				treeSize=j*2;
				break;
			}
			else if(tree[j]==a&&b=='.'&&c!='.')
			{
				tree[j*2+1]=c;
				treeSize=j*2+1;
				break;
			}
			else if(tree[j]==a&&b=='.'&&c=='.')
			{
				break;
			}
			j++;
		}
		j=k;
		tmp++;
	}
	preOrder(1);
	cout<<endl;
	inOrder(1);
	cout<<endl;
	postOrder(1);
	cout<<endl;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1991 트리 순회 질문합니다

jh1125kr 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말