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

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

5639번: 이진 검색 트리

 

아이디어

 

순회와 같은 문제는 DFS로 풀어야겠다고 생각. 입력을 받은 다음 만약 루트, 루트보다 클 경우, 그 중간 이 3개로 분리해서 나누어 재귀함수로 돌리면 해결이 된다. 만약 전위, 중위로 하고 싶으면 print의 위치를 위, 중간 으로 변경하면 가능한 것을 확인 할 수 있다.

 

import sys
sys.setrecursionlimit(10**9)
arr = []
while True:
    try:
        x = int(input())
        arr.append(x)
    except:
        break


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

    left, right = [], []
    
    root = A[0] #맨 앞은 루트
    for i in range(1, len(A)):
        if A[i] > root:
            left = A[1:i]
            right = A[i:]
            break
    else:
    	#모두 root보다 작은 경우
        left = A[1:]
    
    postorder(left)
    postorder(right)
    print(root)

postorder(arr)

 

 

완성