[baekjoon] 백준 5639번 : 이진 검색 트리 (by python 파이썬) 재귀

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

5639번: 이진 검색 트리

 

정답 code

# 이진 검색 트리
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
tree = []

while True:
    try:
        num = int(input())
        tree.append(num)
    except:
        break

def postorder(start,end):
    if start > end:
        return
    mid = end + 1
    for i in range(start+1,end+1):
        if tree[start] < tree[i]:
            mid = i #루트보다 처음으로 커지는수를 오른쪽 프리오더의 시작
            break
    postorder(start + 1, mid - 1) #왼쪽 프리오더 순환  
    postorder(mid, end) # 오른쪽 프리오더 순환
    print(tree[start]) 

postorder(0,len(tree)-1)

 

solution

이번 문제의 핵심은 규칙에 있다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

왼쪽 서브트리의 키는 노드의 키보다 작고, 오른족 서브트리의 키는 노드의 키보다 크다는걸 이용해야된다.

 

전위순회한 입력이 들어오는데 전위순회는 가장 처음은 최상위 노드이고,

이 노드의 오른쪽 서브트리는 노드키보다 커야됨으로 처음으로 노드보다 커지는 수를 찾으면 그 수부터 오른쪽 서브트리가 되고

그 수 전까지는 왼쪽 서브리트리가 된다.

 

이를 이용하여 왼쪽 순환 오른쪽 순환을 해준뒤 출력해주면 후위 순회의 값을 구할 수 있다.

 

 

추가로 몇개의 입력을 받을지 모르는 상태이기때문에,  

try except 예외처리를 이용하여 입력이 없을때 까지 입력을 받아주어야 된다.