[백준] 5639번 이진 검색 트리 (파이썬)

문제링크: https://www.acmicpc.net/problem/5639

문제해결 아이디어

• 전휘순회이므로 루트노드보다 큰 값이 나오면 오른쪽 서브 트리의 시작으로 알수 있다.
• 재귀형식으로 왼쪽 서브트리 순회 -> 오른쪽 서브트리 순회 -> 출력으로 구성

소스코드

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

pre = []

while True:
    try:
        k = int(input())
        pre.append(k)
    except:
        break

def postorder(start, end):
    if start > end:
        return

    mid = end + 1 # 오른쪽 노드가 없는 경우
    for i in range(start+1, end+1):
        if pre[start] < pre[i]: # 오른쪽 트리
            mid = i
            break

    postorder(start+1, mid-1) # 왼쪽
    postorder(mid, end) # 오른쪽
    print(pre[start])

postorder(0, len(pre)-1)