[트리/Python] 5639번: 이진 검색 트리 - 효과는 굉장했다!

5639번: 이진 검색 트리

 

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 재귀

 

 

SOLUTION

import sys
sys.setrecursionlimit(10**6) 

def postorder(start, end):
    if start > end : # 더 이상 탐색할 노드 존재 X
        return
    
    root = preorder_list[start] # 시작 노드
    idx = start + 1
    
    for i in range(idx, end+1):
        # 서브 노드가 뿌리 노드보다 크다면 인덱스 재설정
        # 값이 역전되는 순간 root의 오른쪽 서브노드로 간 것이기 때문
        if preorder_list[i] > root: 
            idx = i
            break
        
    postorder(start+1, idx-1) # 루트의 왼쪽 서브 트리
    postorder(idx, end) # 루트의 오른쪽 서브 트리
    print(root)
    
preorder_list = []
while True:
    try:
        preorder_list.append(int(sys.stdin.readline()))
        
    except:
        break
    
postorder(0, len(preorder_list)-1)