[BOJ / Python] 5639번: 이진 검색 트리

문제: BOJ 5639번

입력
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

풀이

이진 검색 트리의 특성을 이용해, 전위 순회 했을때의 결과로 루트, 왼쪽서브트리, 오른쪽 서브트리를 분리한다.

맨 처음 방문하는 노드가 루트이고, 그 루트보다 작은 값이 왼쪽 서브트리, 더 큰 값은 우측 서브트리 일 것이다.

이 과정을 통해 분리한 서브트리들을 후위순회의 방식대로 방문한다. 왼쪽 서브트리, 우측 서브트리, 그리고 루트.
재귀로 이 과정을 서브트리들에게도 반복한다면 그렇게 출력되는 루트들이 이 문제의 답이다.

최종코드

a = []
sys.setrecursionlimit(10 ** 9)
while True: #입력 개수가 정해지지 않았으므로 try except을 사용한다
    try:
        b = int(input())
    except EOFError:
        break
    a.append(b)


def post(s, e):
    if s > e: #재귀 종료조건
        return
    i = e + 1 #트리사이를 구분하기 위한 인덱스
    for j in range(s + 1, e + 1):
        if a[s] < a[j]: #루트노드보다 더 크면 우측 서브트리이다
            i = j
            break
    post(s + 1, i - 1)  #좌측 서브트리
    post(i, e)          #우측 서브트리
    print(a[s])         #루트 방문


post(0, len(a) - 1)

try except은 처음써보는거라 좀 힘들었다...
PyCharm에서는 EOF입력이 안되더라.. 입력 다 하고 ctrl z누르면 된대서 해봤는데도 안됨.. 결국 onlinegdb에서 해결