5639. 이진 검색 트리

 

 

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

✔ 유형 : 재귀

✔ 문제 풀이: 이진 검색 트리의 특징과 전위 순회를 했을 때의 배열의 규칙을 찾아 범위를 줄여나가 탐색하며 오른쪽 서브트리와 왼쪽 서브트리를 구분해서 문제를 푼다.

 

 

해당 노드보다 큰 원소가 나올 때까지 탐색한다.

큰 원소가 나오면 오른쪽 서브트리를 의미하고 큰 원소의 인덱스부터 오른쪽 서브트리.

해당 노드 인덱스 + 1 부터 큰 원소의 인덱스 -1 까지는 왼쪽 서브트리임을 알 수 있다.

 

 

이제부터 위의 규칙을 이용해 재귀를 돌린다.

 

재귀를 계속 돌리면 결국 리프 노드까지 탐색이 완료되고, 같은 방법으로 왼,오 노드를 구분하여

후위 순회의 순서대로 print를 해주면 된다.

 

 

⬇️ 코드

import sys
input=sys.stdin.readline # input함수 바꾸기
sys.setrecursionlimit(15000) # 10^8 까지 늘림.
# BST
node = list()
        
        
def post_order_print(start, end):
    if start >= end: # 오른쪽 노드가 없을 경우
        return
    
    root = node[start] #root의 노드 번호
    delim = start + 1 #왼오 가 갈리는 인덱스
    
    while delim<end: #인덱스 벗어남녀안되ㅣ니까아
        if root < node[delim]: break #루트보다 큰 친구가 나올때까지 검색
        delim+=1 #delim의 값을 업해주면서 찾음
        
    #while문 빠져나오면~ 루트보다 커졌을때의 index가 delim = 즉 오른쪽 서브트리의 루트를 찾은 것
    post_order_print(start+1, delim)# 왼쪽 서브트리의 루트~ 왼쪽 노드의 마지막 인덱스
    post_order_print(delim, end) #오른쪽노드의 루트~ 끝
    
    print(root) #루트 프린트
         
while True:
    try:
        new_node = int(input())
        node.append(new_node)
    except:
        break
    
post_order_print(0, len(node))