[알고리즘] 백준 5639 '이진 검색 트리' 풀이 _ 파이썬

백준 5639 이진 검색 트리
https://www.acmicpc.net/problem/5639
난이도 : 실버 1
유형 : 트리

문제

이진 검색 트리를 전위 순회한 순서대로 노드가 주어졌을 때, 이 트리를 후위 순회한 순서대로 노드를 출력하는 문제.

풀이

기본적으로 이진 트리 문제였기 때문에 재귀를 사용해서 풀려고 했다.
함수를 만들어서 배열을 넘겨가면서 제일 앞에 있는 수를 루트 노드, 뒤의 배열 중 루트 보다 작은 숫자까지를 왼쪽 배열,나머지를 오른쪽 배열로 3부분으로 나눠주었다.

나눈 부분을 후위 순회하기 위해서 왼쪽 배열을 먼저 재귀로 넘기고, 그 다음 오른쪽 배열을 재귀로 넘기고, 마지막으로 루트 노드 값을 출력했다.

정답 코드

import sys
input = sys.stdin.readline
#recursion error 방지
sys.setrecursionlimit(10**9)

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


def solution(A):
    # 받은 배열 길이가 0이면 return
    if len(A) == 0:
        return

    tempL, tempR = [], []
    # 첫번째 값을 루트 노드로 설정
    mid = A[0]
    # 나머지 배열에 대해 for문을 돌면서 루트보다 커지는 부분을 기록해서 L과 R로 나눈다.
    for i in range(1, len(A)):
        if A[i] > mid:
            tempL = A[1:i]
            tempR = A[i:]
            break
    else:
    	#모두 mid보다 작은 경우
        tempL = A[1:]
    
    #왼쪽, 오른쪽 순으로 재귀 후 루트 노드 값 출력
    solution(tempL)
    solution(tempR)
    print(mid)

solution(arr)