[백준/파이썬] 5639번: 이진 검색 트리

문제

https://www.acmicpc.net/problem/5639

풀이

• 이진 검색 트리
  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
• 이진 검색 트리의 전위 순회 결과를 이용해 후위 순회한 결과 출력

전위 순회는 루트 → 왼쪽 → 오른쪽 방향으로 탐색합니다.
따라서 전위 순회의 첫 번째 값은 항상 루트 노드일 것입니다.
후위 순회는 왼쪽 → 오른쪽 → 루트로 진행합니다.

그리고 문제에 이진 검색 트리의 특징을 잘 살펴 보시면, 왼쪽 서브트리는 항상 루트보다 작은 값들로 이루어져 있고, 오른쪽 서브트리는 항상 루트보다 큰 값들로 이루어져 있습니다.
즉, 전위 순회한 결과를 살펴볼 때 루트보다 큰 값을 발견하게 되면 그 값부터는 오른쪽 서브트리라는 것을 알 수 있습니다.

이 점을 잘 이용하면 트리를 복원하여 후위 순회할 수 있습니다.

if __name__ == "__main__":
    pre = [] # 전위 순회 결과
    while True:
        try:
            pre.append(int(input()))
        except:
            break

• 현재 문제에 노드를 얼마나 넣을 것인지 명시가 되어있지 않기 때문에, try, except로 입력을 받아 줍니다.

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

• pre[start] ~ pre[end] 까지를 하나의 서브트리
• 그래서 시작 인덱스가 끝 인덱스를 초과하게 되면(노드가 없음) 종료

	root = pre[start]

• 전위 순회이므로 첫 번째 값은 항상 루트 노드

    i = start + 1
    
    while i <= end and pre[i] < root:
        i += 1

• 왼쪽 서브트리와 오른쪽 서브트리를 나누기 위해 값이 커지는 구간 탐색
• 즉, 루트보다 작은 값들은 왼쪽 서브트리
• 루트보다 큰 값이 처음 나오는 위치 i부터는 오른쪽 서브트리

    pst(start + 1, i - 1)
    pst(i, end)
    print(root)

• 후위 순회 시작
  • 왼쪽 서브트리 탐색
  • 오른쪽 서브트리 탐색
  • 루트 노드 출력

---

마지막으로 깊이 제한을 늘려줘야 합니다 ‼

기본적으로 파이썬의 재귀 깊이 제한은 약 1000이지만, 문제에 명시된 노드의 수는 최대 10000개이므로 깊이 제한을 늘려줘야 합니다.

안 그러면 RecursionError가 발생하게 됩니다.

코드

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

def pst(start, end):
    if start > end:
        return
    
    root = pre[start]
    i = start + 1
    
    while i <= end and pre[i] < root:
        i += 1
        
    pst(start + 1, i - 1)
    pst(i, end)
    print(root)

if __name__ == "__main__":
    pre = []
    while True:
        try:
            pre.append(int(input()))
        except:
            break
        
    pst(0, len(pre) - 1)