백준 5639번: 이진 검색 트리(Python, 파이썬, 이진 트리, 후위순회)

문제

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

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.

• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.

• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

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

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

입력

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

출력

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

문제풀이

트리를 하나 생성

문제에서 입력을 받는 것을 그대로 트리에 추가한다.

그리고 현재 트리를 후위순회로 출력한다.

import sys
sys.setrecursionlimit(1_000_000)

class Node:
    def __init__(self, value):
        self.value = value
        self.parent = None
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def add(self, value):
        if self.root is None:
            node = Node(value)
            self.root = node
            return

        current = self.root

        while True:
            if value < current.value:
                if current.left is None:
                    new_node = Node(value)
                    current.left = new_node
                    new_node.parent = current
                    return
                else:
                    current = current.left
            elif value > current.value:
                if current.right is None:
                    new_node = Node(value)
                    current.right = new_node
                    new_node.parent = current
                    return
                else:
                    current = current.right

            else:
                return

    def postorder_print(self, node = None):
        if node is None:
            node = self.root

        if node is None:
            return
        
        if node.left is not None:
            self.postorder_print(node.left)
        if node.right is not None:
            self.postorder_print(node.right)
        print(node.value)

tree = BinaryTree()

inputs = list(map(int,sys.stdin.read().split()))

for i in inputs:
    tree.add(i)

tree.postorder_print()