[C++] 1991. 트리 순회

트리와 3가지 순회를 구현해보는 문제이다.

사실 처음엔 vector를 이용해서 구현해보려고 했는데, (멍청)

생각해보니 노드를 찾으려면 모든 vector를 순회해야 하므로 복잡도가 엄청 들게 생겼다..

그래서, unordered_map을 이용하기로 했다.

hash특성상 키에 접근하는 시간이 O(1) 상수시간이므로 빠르게 접근이 가능하다.

다만, 정렬은 필요없으므로 unordered를 사용했다.

 

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

unordered_map<string, pair<string,string> > tree;

//root-left-right
void preOrder(const string& node)
{
    //node가 .이면 자식이 없으므로 return
    if(node == ".") return;
    cout << node;

    preOrder(tree[node].first);
    preOrder(tree[node].second);
}

//left-root-right
void inOrder(const string& node)
{
    if(node == ".") return;

    inOrder(tree[node].first);
    cout << node;
    inOrder(tree[node].second);
}

//left-right-root
void postOrder(const string& node)
{
    if(node == ".") return;

    postOrder(tree[node].first);
    postOrder(tree[node].second);
    cout << node;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N; cin >> N;
    for(int i=0; i<N; i++) {
        string root, left, right;
        cin >> root >> left >> right;
        tree[root] = make_pair(left, right);
    }

    preOrder("A");
    cout << "\n";
    inOrder("A");
    cout << "\n";
    postOrder("A");

    return 0;
}