[BOJ] 1991 - 트리 순회 (C++)

문제

트리 순회

코드

#include <iostream>
#include <unordered_map>

using namespace std;

int N;

void preorder(unordered_map <char, char>& left, unordered_map <char, char>& right, char node){
    if (node == '.') return;
    cout << node;
    preorder(left, right, left[node]);
    preorder(left, right, right[node]);
}

void inorder(unordered_map <char, char>& left, unordered_map <char, char>& right, char node){
    if (node == '.') return;
    inorder(left, right, left[node]);
    cout << node;
    inorder(left, right, right[node]);
}

void postorder(unordered_map <char, char>& left, unordered_map <char, char>& right, char node){
    if (node == '.') return;
    postorder(left, right, left[node]);
    postorder(left, right, right[node]);
    cout << node;
}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    unordered_map <char, char> left, right;
    char p, l, r;

    cin >> N;

    for (int i = 0; i < N; i++){
        cin >> p >> l >> r;
        left[p] = l; right[p] = r;
    }

    preorder(left, right, 'A'); cout << endl;
    inorder(left, right, 'A'); cout << endl;
    postorder(left, right, 'A');

    return 0;
}

접근

이 문제는 left, right child를 나눠서 저장한 것이 핵심이었다. 전위, 중위, 후위 순회를 재귀로 구현하는 것은 큰 문제가 아니었고 오히려 이를 어떻게 저장해서 재귀함수에서 활용할 것인가가 문제였는데 unordered_map을 통해 해결할 수 있었다.