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

문제

 

풀이

전위 순회한 결과

50 30 24 5 28 45 98 52 60

 

첫 번째 원소가 루트 노드 (전위 순회의 성질에 의해)

왼쪽 서브 트리 = 루트 노드보다 작은 원소인 경우

오른쪽 서브 트리 = 루트 노드보다 큰 원소의 경우

 

전위 순회를 했으므로 루트 노드보다 큰 원소가 나오는 지점이 왼쪽 서브 트리와 오른쪽 서브 트리를 나누는 지점과 같다.

50 30 24 5 28 45 98 52 60

초록 = 루트 노드, 빨강 = 왼쪽 서브 트리, 파랑 = 오른쪽 서브 트리

 

위 결과를 활용해 후위 순회를 해주면 된다.

 

코드

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

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

def post(start, end):
    if start > end:
        return
    mid = end + 1
    for i in range(start + 1, end + 1):
        if pre[i] > pre[start]:
            mid = i
            break
    post(start + 1, mid - 1) #왼쪽 트리
    post(mid, end) #오른쪽 트리
    print(pre[start]) #루트 노드

post(0, len(pre) - 1)

mid를 end + 1로 초기화하는 이유

 

만약 모든 원소가 루트 노드보다 작은 경우

post(start + 1, mid - 1) : start + 1, end 가 삽입, 즉 루트 노드를 제외한 트리

post(mid, end) : end + 1, end 가 삽입되어 if start > end: return에 의해 리턴됨 이는 오른쪽 노드가 없음을 의미

 

마무리

재귀는 너무 까다롭고, 애초에 문제 접근 방식도 몰라서 쩔쩔 헤매다가 구글링 해서 겨우 풀었다...