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

해당 글은 백준 5639번 문제 '이진 검색 트리'을 다룬다.

문제

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

5639번: 이진 검색 트리

 

설명

전위순회 결과를 확인하면서, left를 root, right까지의 값을 확인하며 큰 값이 있다면 해당 값을 기준으로 2부분으로 쪼개서 재귀를 돌린다. 해당 과정을 left > right가 될 때까지 반복한다.

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

pre_order = []
while True:
    try:
        pre_order.append(int(input()))
    except:
        break

def postorder(left, right):
    if left > right:
        return
    else:
        root = pre_order[left]
        div = right + 1
        for i in range(left+1, right+1):
            if root < pre_order[i]:
                div = i
                break
        postorder(left+1, div-1)
        postorder(div, right)
        print(root)

postorder(0, len(pre_order)-1)