BOJ 5639 이진 검색 트리

https://www.acmicpc.net/problem/5639
시간 2초, 메모리 128MB
input :

• 전위 순회한 결과
• 노드의 수는 10,000개 이하

output :

• 후위 순회한 결과를 한 줄에 하나씩 출력

---

런타임 에러가 빗발쳤다...
입력이 들어오는 것이 이진 검색 트리이기 때문에, root 노드와 비교를 할 경우
왼쪽에 존재하는 것은 다 root 보다 작다, 그리고 이 기준을 찾을 수 있다.
그렇게 분류를 하면서 왼쪽, 오른쪽을 구분해준다.

그렇게 해서 leaf 노드까지 방문을 할 경우 현재 노드를 출력해주고,
leaf노드가 없을 떄, 즉 배열의 길이가 1보다 작아지면 그냥 return 해준다.
root 노드가 제일 큰 경우도 판별 해주기 위해서 mid 의 초기화는 len(array)로 해준다.

가장 큰 문제는 try except 거는 것이였다.
sys로 입력을 받으려니 계속 개행 문자가 따라 들어와서 인지 런타임 에러가 발생했다.
input()으로 입력을 받으니 해결되었다.

슬라이싱을 해서 하지 말고 배열은 유지하고, idx만을 가지고 할 경우 메모리를 많이 줄일 수 있을 거 같다.

import sys
sys.setrecursionlimit(100000)

def dfs(array):
    if len(array) == 1:
        print(array[0])
        return

    if len(array) < 1:
        return

    root = array[0]
    mid = len(array)
    for i in range(1, len(array)):
        if array[i] > root:
            mid = i
            break
    dfs(array[1:mid])
    dfs(array[mid:])
    print(root)


data = []
while True:
    try:
        temp = int(input())
        data.append(temp)
    except EOFError:
        break
dfs(data)