[백준] 1991번. 트리 순회 (C++)

문제

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

---

풀이

[재귀]

preorder = node  Left  Right

inorder = Left  node  Right

postorder =  Left  Right  node

 

+) 처음에 "2번 무식한 코드" 처럼 만들었는데

암만봐도 더 나은 방법이 있을 것 같아서 1번으로 바꿈

---

코드

1️⃣ 깔끔한 코드

#include <iostream>
#include <unordered_map>
#include <vector>
#include <stack>
using namespace std;
unordered_map<char, pair<char, char>>tree;

void preorder(char nowNode) {
    if (nowNode == '.')return;
    cout << nowNode;
    preorder(tree[nowNode].first);
    preorder(tree[nowNode].second);
}

void inorder(char nowNode) {
    if (nowNode == '.')return;
    inorder(tree[nowNode].first);
    cout << nowNode;
    inorder(tree[nowNode].second);
}

void postorder(char nowNode) {
    if (nowNode == '.')return;
    postorder(tree[nowNode].first);
    postorder(tree[nowNode].second);
    cout << nowNode;
}

int main() {

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


    //CHECK
    //preorder
    preorder('A');
    cout << "\n";
    //inorder
    inorder('A');
    cout << "\n";
    //postorder
    postorder('A');

}

 

 

2️⃣ 무식한 코드

#include <iostream>
#include <map>
#include <vector>
#include <stack>
using namespace std;
int N;

void preorder(map<char, pair<char, char>>tree) {
    string result = "";
    vector<int>visited(N+1, 0);
    stack<char>q;
    q.push('A');
    while (!q.empty()) {

        //root
        char now = q.top();
        if (visited[now - 65] == 0) {
            result += now;
            visited[now - 65] = 1;
        }
        
        //left
        char next = '.';
        if (tree[now].first != '.') {
            next = tree[now].first;
            tree[now].first = '.';
        }
        //right
        else if (tree[now].second != '.') {
            next = tree[now].second;
            tree[now].second = '.';
        }

        //자식이 없음
        if (next == '.') {
            q.pop();
        }
        else {
            q.push(next);
        }
    }
    cout << result << "\n";
}


void inorder(map<char, pair<char, char>>tree) {
    string result = "";
    stack<char>q;
    q.push('A');
    while (!q.empty()) {

        char now = q.top();
        char next = '.';

        //left
        if (tree[now].first != '.') {
            next = tree[now].first;
            tree[now].first = '.';
            q.push(next);
        } 
        //no left
        else {
            result += now;
            q.pop();
            if (tree[now].second != '.') {
                next = tree[now].second;
                tree[now].second = '.';
                q.push(next);
            }
        }
    }
    cout << result<<"\n";
}



void postorder(map<char, pair<char, char>>tree) {
    string result = "";
    stack<char>q;
    q.push('A');
    while (!q.empty()) {

        //root
        char now = q.top();

        //left
        char next = '.';
        if (tree[now].first != '.') {
            next = tree[now].first;
            tree[now].first = '.';
        }
        //right
        else if (tree[now].second != '.') {
            next = tree[now].second;
            tree[now].second = '.';
        }

        //자식이 없음
        if (next == '.') {
            result += now;
            q.pop();
        }
        else {
            q.push(next);
        }
    }
    cout << result<<"\n";
}

int main() {

    //INPUT
    cin >> N;
    map<char, pair<char, char>>tree;
    char root, left, right;
    for (int i = 0; i < N; i++) {
        cin >> root >> left >> right;
        tree[root] = { left,right };
    }

    //CHECK
    //preorder
    preorder(tree);
    //inorder
    inorder(tree);
    //postorder
    postorder(tree);
    
}