[백준] 5639번 이진 검색트리

문제 링크: https://www.acmicpc.net/problem/5639

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

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

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

문제 접근

이진 검색 트리 문제이다.

전위 순회는 첫번째 들어오는 숫자가 root이다라는 점에서 시작한다.
이진 검색트리이기 때문에, root의 왼쪽에는 root보다 작은 숫자가 들어가고 오른쪽에는 큰 숫자가 들어간다는 특징을 이용해, 입력으로 트리를 구성한다.
그리고 구성한 트리를 postorder로 출력해준다.

코드 구현(c++)

#include <iostream>
#include <cstring>
#include <stdio.h>

using namespace std;

int tree[1000001][2];

void postorder(int n){
    if(n == 0) return;

    postorder(tree[n][0]);
    postorder(tree[n][1]);

    cout << n << "\n";
}

void preorder(int root, int cur){
    if(cur > root ){
        if(tree[root][1] == 0){
            tree[root][1] = cur;
            return;
        }
        else{
            preorder(tree[root][1], cur);
        }
    }
    else{
        if(tree[root][0] == 0){
            tree[root][0] = cur;
            return;
        }
        else{
            preorder(tree[root][0], cur);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int root , n;
    cin >> root;
    memset(tree, 0, sizeof(tree));
    while(cin >> n){
        preorder(root,n);
    }
    postorder(root);
}

평가

메모리를 너무 많이 사용했다. 다른 사람들의 코드를 참고해 메모리를 줄여봐야겠다.
무한정의 입력을 받을 때는 while(cin >> n) 형태로 받아줘서, n이 들어올때까지만 받을 수 있다.