[알고리즘/파이썬] 백준 5639 - 이진 검색 트리

문제

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

5639번: 이진 검색 트리

 

풀이

트리 공포증이 있는 나는 조금 쫄았지만 다행히 맨 앞 노드 외에 뒤에서 맨앞 노드보다 작은 부분은 왼쪽으로, 큰 부분은 오른쪽으로 분류해주면 되겠다..는 생각을 했고 최근에 트리 전위순회 관련 재귀 문제를 풀었어서 금방 적용할 수 있었다!

 

예를 들어 50 30 24 5 28 45 98 52 60 라는 전위 순회 값이 있을 때, 루트 노드(맨 앞 노드)인 50을 기준으로 작은건 30부터 45까지, 큰 부분은 98부터 60까지이다.

그럼 작은 부분인 30 24 5 28 45를 다시 가져오면 루트 노드(맨 앞 노드)인 30을 기준으로 작은건 24부터 28까지, 큰 건 45이다. 이런 식으로 재귀로 탐색하면 되고, 후위 순회는 (왼쪽-오른쪽-루트) 순으로 출력해야 하므로 왼쪽 재귀, 오른쪽 재귀, 현재 루트 노트 출력 순으로 입력해줬다.

 

 

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

arr = []

while True:
    try:
        x = int(input())
        arr.append(x)
    except:
        break


def output(A):
    if len(A) == 0:
        return

    tmpL, tmpR = [], []


    root = A[0]
    for i in range(1, len(A)):
        if A[i] > root:
            # 작은 부분 - 왼쪽 노드
            tmpL = A[1:i]
            # 큰 부분 - 오른쪽 노드
            tmpR = A[i:]
            break
    else:
    	#모두 root보다 작은 경우
        tmpL = A[1:]
    
    #왼쪽, 오른쪽 순으로 재귀 후 루트 노드 값 출력
    output(tmpL)
    output(tmpR)
    print(root)

output(arr)