BaekJoon 1991번: 트리 순회

풀이법

1) 재귀를 통해 전위, 중위, 후위를 순회한 값을 구한다.

2) node의 값을 뽑는 위치의 차이이기에 일종의 공식처럼 알아 두면 좋을 듯 하다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;

int n;
struct node {
	char left;
	char right;
};
struct node arr[27];

void pre(char root)
{
	if (root == '.')
		return;
	cout << root;
	pre(arr[root].left);
	pre(arr[root].right);
}
void middle(char root)
{
	if (root == '.')
		return;
	middle(arr[root].left);
	cout << root;
	middle(arr[root].right);
}
void post(char root)
{
	if (root == '.')
		return;
	post(arr[root].left);
	post(arr[root].right);
	cout << root;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		char a, b, c;
		cin >> a >> b >> c;
		arr[a].right = c;
		arr[a].left = b;
	}
	pre('A');
	cout << "\n";
	middle('A');
	cout << "\n";
	post('A');
}

한계점 및 개선사항

Stack으로 구현하려 했으나 너무 복잡하여 실패했다. 예외 처리에 대해서 조금 더 꼼꼼하게 집중할 필요성을 느꼈다.

때로는 재귀가 더 깔끔한 코드가 나올 수 있는 것을 알았으며 추후 이를 잘 활용해 봐야겠다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest