백준 문제 풀이 - 이진 검색 트리 5639번

📜 문제 이해하기

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

💡 문제 재정의

전위 순회로 방문된 노드를 후위 순회한 결과를 구하자

✏️ 계획 수립

이진 검색 트리를 만들 수 있다면 간단한 문제이다.
전위 순회는 입력으로 들어온 값과 똑같기 때문에 이 입력을 그대로 이진 트리에 넣어주고 이진 트리에서 후위 순회한 결과를 확인하면 된다.

💻 계획 수행

#include <iostream>
using namespace std;


class Node{
public:
    int data;
    Node* left;
    Node* right;

    Node(int _data, Node* _left, Node* _right) : data(_data), left(_left), right(_right)
    { }
};


class BinaryTree{
public:
    Node* root;

    BinaryTree(){
        root = nullptr;
    }

    bool Insert(int insert_num){
        if (root == nullptr){
            root = new Node(insert_num, nullptr, nullptr);
            return true;
        }

        else {
            return InsertRecursion(root, insert_num);
        }
    }

    bool InsertRecursion(Node *cur_node, int num){
        // 현재 노드가 nullptr이면 노드 생성 후 넣기
        // 현재 노드와 비교했을 때 작으면 왼쪽 크면 오른쪽 노드와 비교
        if (num < cur_node->data) {
            if (cur_node->left == nullptr)
                cur_node->left = new Node(num, nullptr, nullptr);
            else
                InsertRecursion(cur_node->left, num);
        }
        else {
            if (cur_node->right == nullptr)
                cur_node->right = new Node(num, nullptr, nullptr);
            else
                InsertRecursion(cur_node->right, num);
        }

        return true;
    }

    void PostOrder(Node *cur_node){
        if (cur_node->left != nullptr)
            PostOrder(cur_node->left);
        if (cur_node->right != nullptr)
            PostOrder(cur_node->right);
        cout << cur_node->data << endl;
    }
};


int main() {
    BinaryTree bt;
    int n;
    while (cin >> n)
        bt.Insert(n);
    bt.PostOrder(bt.root);
    return 0;
}

🤔 회고

C++로 트리를 처음 짜봤는데 역시 객체 동적 할당 개념이 헷갈려서 오래걸렸다..
이럴때는 파이썬이 그립지만 열심히 C++ 연습을 해야겠다.