[백준] 5639 : 이진 검색 트리

문제

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

이진검색트리

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 중복된 노드가 없어야 한다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.
• 이진 검색 트리를 순회할 때는 중위순회(inorder) 방식을 쓰는데, (왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리) 이렇게 하면 이진 검색 트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다.
• 가장 왼쪽엔 최솟값이, 가장 오른쪽엔 최대값이 위치하게 된다.

출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

정리

풀이

import sys
sys.setrecursionlimit(10**6)

#입력받을 원소 리스트
num_list=[]
while True:
    try:
        num=int(input())
        num_list.append(num)
    except:
        break

def postorder(left,right):
    #순서 역전시 종료
    if left>right:
        return
    else:
        for i in range(left+1,right+1): # 루트 노드인 left 노드를 빼고 right 노드 인덱스까지 돎
            
            #현재 원소가 루트 노드보다 크다면 그 전까지는 왼쪽 서브 트리,
            #현재 원소 이후(이상)는 오른쪽 서브 트리이다.
            
            if num_list[left] < num_list[i]: # num_list[left]: 루트 노드 | num_list[i]: 현재 노드
                mid=i # 오른쪽 서브트리 노드의 인덱스
                break
        else:
            mid=right+1 
            # 오른쪽 서브트리의 가장 큰 원소의 인덱스
            # 오른쪽 서브트리가 없을 경우를 대비한 것
            
        postorder(left+1,mid-1) # 좌측 서브트리 | left 인덱스는 루트 노드이므로 left+1 인덱스부터 해줘야
        postorder(mid,right) # 우측 서브트리
        print(num_list[left]) # 루트 노드 출력

postorder(0,len(num_list)-1)