[Backjoon] 5639 이진 검색 트리 Python 문제 풀이

출처 : 5639번 이진 검색 트리

문제해석

전위 순회 결과

50 30 24 5 28 45 98 52 60

첫 원소가 루트 노드(전위 순회)
왼쪽 서브 트리는 루트 노드보다 작은 원소
오른쪽 서브 트리는 루트 노드보다 큰 원소

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

50 /30 24 5 28 45/ 98 52 60

50=루트 노드, 3045=왼쪽 서브트리, 9860= 오른쪽 서브트리

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

해답코드

#이진 검색 트리
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에 의해 리턴됨 이는 오른쪽 노드가 없음을 의미