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

5639번 - 이진 검색 트리

문제 이해

이진 검색 트리의 전위순회 preorder가 주어지면, 후위순회한 결과를 출력하면 되는 문제.

접근

개수나 입력의 끝은 나타내는 수가 주어지지 않아 EOF를 이용해 입력을 받아야 한다. 파이썬의 경우 sys.stdin.readlines()를 통해 각 줄을 원소로 하는 리스트로 입력을 받을 수 있고, map을 통해 정수로 처리하여 사용하면 편리하다.

전위순회의 정의에 따라 맨 앞부분이 root노드가 될 것이고, 나머지 부분들이 왼쪽 자식부분, 오른쪽 자식부분으로 나뉘게 될 텐데, 이진 검색 트리의 정의에 따라 나머지 부분 중 처음 나오는 root값보다 큰 값이 오른쪽 자식부분의 루트노드가 된다.

이를 이용해 재귀로 구현해 주면 된다.

파이썬 자체릐 재귀 깊이의 제한이 있어 sys.setrecursionlimit()을 통해 재귀 깊이를 충분히 늘려주지 않으면 RecursionError 런타임 에러가 나게 된다. 그렇다고 너무 크게 늘려 재귀를 위한 메모리를 과하게 잡는다면 문제 자체의 메모리 제한에 걸려 틀리게 된다. 보통의 경우 $10^5$ 정도면 적당하다.

정답 코드

import sys
sys.setrecursionlimit(10**5)

preorder = [*map(int, sys.stdin.readlines())]

def postorder(l, r):
    if l > r:
        return
    if l == r:
        print(preorder[l])
        return
    root = preorder[l]
    for i in range(l+1, r+1):
        if preorder[i] > root:
            postorder(l+1, i-1)
            postorder(i, r)
            print(root)
            return
    postorder(l+1, r)
    print(root)


postorder(0, len(preorder)-1)