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

1. 문제

5639번: 이진 검색 트리

2. 개요

이진 검색 트리를 전위 순회한 결과가 순서대로 주어졌을 때,

이를 후위 순회한 결과를 한 줄에 하나씩 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

처음에는 루트를 1로 하고, 왼쪽 자식이 *2, 오른쪽 자식이 *2 + 1 인 형식의 배열로 만드려 했다.

그런데 전위 순회한 결과가 1, 2, 3, … , 10000 이면 배열의 크기가 2^10000 을 넘어가길래 딕셔너리를 이용했다.

딕셔너리의 키는 해당 노드의 값, 밸류는 자식들의 값을 들고 있게 한다.

먼저 전위 순회한 결과를 바탕으로 트리를 작성한다.

입력받은 값이 현 탐색중인 노드보다 작다면 왼쪽으로, 크다면 오른쪽으로 이동하다가 빈 공간이 있다면 그곳에 넣어준다.

트리를 완성했다면 후위순회하며 해당 노드의 값을 한 줄에 하나씩 출력한다.

3-2. Python

import sys
sys.setrecursionlimit(25000)

binarytree = dict()
root = None

while True:
    try:
        n = int(sys.stdin.readline())
        binarytree[n] = [-1, -1]

        if root == None:
            root = n

        now = root

        while True:
            if n == root:
                break

            lchild = binarytree[now][0]
            rchild = binarytree[now][1]

            if n > now:
                if rchild == -1:
                    binarytree[now][1] = n
                    break

                now = rchild

            else:
                if lchild == -1:
                    binarytree[now][0] = n
                    break
                now = lchild

    except:
        break

def postorder(num):
    for node in binarytree[num]:
        if node in binarytree:
            postorder(node)

    print(num)

postorder(root)

3-3. C#

namespace boj_5639
{
    internal class Program
    {
        static Dictionary<int, int[]> binaryTree = new Dictionary<int, int[]>();
        static int root = -1;

        static void Main(string[] args)
        {
            while (true)
            {
                try
                {
                    int n = int.Parse(Console.ReadLine());
                    binaryTree[n] = new int[2];

                    if (root == -1)
                        root = n;

                    int now = root;

                    while (true)
                    {
                        if (n == root)
                            break;

                        int lchild = binaryTree[now][0];
                        int rchild = binaryTree[now][1];

                        if (n > now)
                        {
                            if (rchild == 0)
                            {
                                binaryTree[now][1] = n;
                                break;
                            }

                            now = rchild;
                        }

                        else
                        {
                            if (lchild == 0)
                            {
                                binaryTree[now][0] = n;
                                break;
                            }

                            now = lchild;
                        }

                    }
                }

                catch
                {
                    break;
                }
            }

            PostOrder(root);
        }

        static void PostOrder(int num)
        {
            foreach (int node in binaryTree[num])
            {
                if (binaryTree.ContainsKey(node))
                    PostOrder(node);
            }

            Console.WriteLine(num);
        }
    }
}