백준 1991 : 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

기본적인 트리 순회 문제다.

재귀적인 방법으로 전위, 중위, 후위 순회를 구현했다.

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> tree[26];

string preorder(int cur) {
	string ret = "";

	ret.push_back('A' + cur);
	if (tree[cur][0] > 0) ret += preorder(tree[cur][0]);
	if (tree[cur][1] > 0) ret += preorder(tree[cur][1]);
	
	return ret;
}

string inorder(int cur) {
	string ret = "";

	if (tree[cur][0] > 0) ret += inorder(tree[cur][0]);
	ret.push_back('A' + cur);
	if (tree[cur][1] > 0) ret += inorder(tree[cur][1]);
	
	return ret;
}

string postorder(int cur) {
	string ret = "";

	if (tree[cur][0] > 0) ret += postorder(tree[cur][0]);
	if (tree[cur][1] > 0) ret += postorder(tree[cur][1]);
	ret.push_back('A' + cur);

	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	char c1, c2, c3;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> c1 >> c2 >> c3;
		if (c2 == '.') c2 = 'A' - 1;
		if (c3 == '.') c3 = 'A' - 1;
		tree[c1 - 'A'].push_back(c2 - 'A');
		tree[c1 - 'A'].push_back(c3 - 'A');
	}

	cout << preorder(0) << '\n';
	cout << inorder(0) << '\n';
	cout << postorder(0);

	return 0;
}

메모리: 2024 kb

시간: 0 ms