백준 5639번 : 이진검색트리 (Python, 파이썬) - 미완성 코드

https://www.acmicpc.net/problem/5639

전위 순회(Preorder traversal)는 기존의 트리구조를 그대로 보존해 다른 곳으로 옮길 수 있다는 장점이 있다. 이 문제에선 그 장점을 이용한다. 전위 순회 값을 받아 그대로 투입하면 온전한 트리구조를 만들 수 있다. 그 트리를 다시 후위 순회로 뽑아내기만 하면 된다.

하지만 보다시피 '실패' 예제 입력과 예제 출력을 충실하게 반영하므로 잘못 짠 것 같진 않다. 하지만 미세한 반례가 있는지 계속 틀리다고 한다. 내 생각엔 지금까지 풀어본 문제에 비해 이 문제의 입력 조건이 특이해서 그런 것 같다.

class Node:
    def __init__(self, item):
        self.val = item
        self.left = None
        self.right = None
 
class BinaryTree:
    def __init__(self):
        self.head = Node(None)
        self.postorder_list = []
        self.judge_list = []
    
    def add(self, item):
        if self.head.val is None:
            self.head.val = item
        else:
            self.__add_node(self.head, item)
 
 
    def __add_node(self, cur, item):
        if cur.val > item:
            if cur.left is not None:
                self.__add_node(cur.left, item)
            else:
                cur.left = Node(item)
        elif cur.val < item:
            if cur.right is not None:
                self.__add_node(cur.right, item)
            else:
                cur.right = Node(item)
    
    def postorder_traverse(self): 
        if self.head is not None:
            self.__postorder(self.head)
 
    def __postorder(self, cur):
        if cur.left is not None:
            self.__postorder(cur.left)
 
        if cur.right is not None:
            self.__postorder(cur.right)
 
        self.postorder_list.append(cur.val)
bt = BinaryTree()
count = 0
while count <= 10000:
    num = int(input())
    if num < (10**6) and num not in bt.judge_list:
        bt.add(num)
        count += 1
        bt.judge_list.append(num)
bt.postorder_traverse()
for i in bt.postorder_list:
    print(i)