1. 문제 설명

이진 검색 트리

2. 문제 분석

전위, 중위, 후위는 재귀를 통해 푸는 게 보다 직관적이다. (서브 트리라고 가정해서) 그 트리의 루트, 왼쪽 서브트리, 오른쪽 서브트리가 있을 때 출력 기준이 루트 노드라고 하자. 재귀를 주는 순서는 각 탐색 방향이다. (즉 중위라면 왼쪽, 루트 출력, 오른쪽 재귀 호출 등)

3. 나의 풀이

import sys

sys.setrecursionlimit(10**6)
numbers = []
while True:
    try:
        num = int(sys.stdin.readline())
    except: break

    numbers.append(num)

def post(left, right):
    if left > right: return

    mid = right + 1
    # right를 서브 트리의 오른쪽 끝이라 할 때
    for idx in range(left+1, right+1):
        if numbers[left] < numbers[idx]:
            # 서브 트리의 루트 노드가 되는 idx를 찾는다.
            mid = idx
            break
    post(left+1, mid-1)
    # 왼쪽 서브트리
    post(mid, right)
    # 오른쪽 서브트리
    print(numbers[left])
    # 루트 노드 출력

post(0, len(numbers)-1)