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

5639번: 이진 검색 트리 (acmicpc.net)

5639번: 이진 검색 트리

 

import sys

sys.setrecursionlimit(10 ** 9) #재귀 많이 할 수 있게

def post_order(start,end):

    if start>end: #기저조건

        return

   

    mid = end+1 #오른쪽 트리의 루트노드 초기화

    for i in range(start+1,end+1):

        if arr[start]<arr[i]:

            mid = i #루트보다 커지는 지점이 오른쪽 트리의 루트노드

            break

    post_order(start+1, mid-1) #왼쪽 트리 방문

    post_order(mid, end) #오른쪽 트리 방문

    print(arr[start]) #끝까지 오면 노드 출력 시작

arr=[]

while True: #몇개를 입력받을지 모르기때문에 try except

    try:

        arr.append(int(input()))

    except: #더이상 입력받지 않으면

        break

post_order(0,len(arr)-1)