백준 5639번 문제 ( 이진 검색 트리 )

문제 출처 : https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

이 문제는 전위 순회한 결과를 보고 후위 순회한 결과를 출력하는 것이다.

전위 순회는 자기 자신을 맨 처음 출력하기 때문에 root는 맨 처음 나온 수가 되고

후위 순회는 좌, 우측을 다 보고 출력을 하기 때문에 

아래와 같은 풀이로 풀 수 있다.

 

#include<stdio.h>
#pragma warning(disable:4996)
int tree[1000001][3];
void insert(int root, int num)
{
    if (num > root)
    {
        if (tree[root][1] == 0)
            tree[root][1] = num;
        else
            insert(tree[root][1],num);
        
    }
    else if (num < root)
    {
        if (tree[root][0] == 0)
            tree[root][0] = num;
        else
            insert(tree[root][0],num);
    }
}
void postorder(int start)
{
    if (tree[start][0] != 0)
        postorder(tree[start][0]);
    if (tree[start][1] != 0)
        postorder(tree[start][1]);
    printf("%d\n", start);
}
int main()
{
    int num;
    int root;
    scanf("%d", &root);
    while (scanf("%d", &num) == 1)
    {
        insert(root, num);
    }
    
    postorder(root);
}