1231. [S/W 문제해결 기본] 9일차 - 중위순회

 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD&categoryId=AV140YnqAIECFAYD&categoryType=CODE

SW Expert Academy

 

 

트리 탐색이 어떻게 동작하는지 그대로 구현하면 되는 문제.

 

 

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

struct Node {

	char c;
	int left;
	int right;

};

string str;

Node arr[101];
int parent[101];
bool visit[101];

void DFS(int cur)
{
	if (cur == 0)
	{
		return;
	}
	if (arr[cur].left != -1 && !visit[arr[cur].left])
	{
		DFS(arr[cur].left);
	}
	else
	{
		if (!visit[cur])
		{
			visit[cur] = true;
			str += arr[cur].c;
		}

		if (arr[cur].right != -1 && !visit[arr[cur].right])
		{
			DFS(arr[cur].right);
		}
		else
		{
			DFS(parent[cur]);
		}
	}


}


int main(int argc, char** argv)
{
	int test_case;

	
	for (test_case = 1; test_case <= 10; ++test_case)
	{
		int N;
		str.clear();
		memset(visit, 0, sizeof(visit));
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			int idx;
			cin >> idx;
			char c;
			cin >> c;

			int a = -1;
			int b = -1;

			if (idx * 2 < N)
			{
				cin >> a >> b;
				parent[a] = idx;
				parent[b] = idx;
			}
			else if (idx * 2 == N)
			{
				cin >> a;

				parent[a] = idx;
			}

			arr[idx] = {c, a,b };
		}
		DFS(1);
		cout <<"#" << test_case<<" " << str << endl;
		
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}