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

#문제링크

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

5639번: 이진 검색 트리

#나의풀이

import sys

sys.setrecursionlimit(10**9)

def post(start, end):
    if start > end:
        return
    mid = end + 1
    for i in range(start+1, end+1):
        if Num[i] > Num[start]:
            mid = i
            break

    post(start+1, mid-1)
    post(mid, end)
    print(Num[start])

if __name__=="__main__":
    Num = list()
    while True:
        try:
            N = int(input())
            Num.append(N)
        except:
            break

    post(0, len(Num)-1)

#해설

    while True:
        try:
            N = int(input())
            Num.append(N)
        except:
            break

값을 계속 입력받고 더이상 입력받지 못하면 break로 끝낸다.

 

def post(start, end):
    if start > end:
        return
    mid = end + 1
    for i in range(start+1, end+1):
        if Num[i] > Num[start]:
            mid = i
            break

start가 end보다 더 크다는건 탐색 범위가 끝났다는 것으로 바로 return으로 종료시키고

 

mid = end+1을 한 이유는 아래 반복문에서 현재보다 더 큰 값을 찾고 오른쪽 자식 노드로 mid를 설정할것인데 만약 나오지 않는다면 오른쪽은 없는것으로 탐색할 필요가 없으니 end+1로 end보다 크게 설정해주었다.

 

반복문을 돌면서 현재 root 보다 큰 값을 찾고 찾았다면 mid로 설정한다

 

    post(start+1, mid-1)
    post(mid, end)
    print(Num[start])

후위순열 출력하는 방법 첫번째 post는 왼쪽노드를 찾는것 두번째는 오른쪽노드를 찾는것