[백준] 5639번_이진 검색 트리 (파이썬/Python)

5639번_이진 검색 트리
https://www.acmicpc.net/problem/5639

문제 요약
1. 이진 검색 트리에서 전위 순회(루트->왼쪽->오른쪽)한 값을 순서대로 입력
2. 입력 종료 조건이 없음 (입력 크기가 정해져있지 않음)
2. 입력 값을 이용하여 후위 순회(왼쪽->오른쪽->루트)한 값으로 출력

처음에 전위 순회해서 트리 전체를 만들고 후위 순회하려니까 시간 초과가 발생했다. 그래서 왼쪽 노드 < 루트 < 오른쪽 노드인 특성을 이용해서 입력값을 바로 확인하여 출력했다. (결국 다른 풀이 참고,,)

import sys
sys.setrecursionlimit(10**9)
nums = []
while True:                            
    try:
        nums.append(int(sys.stdin.readline()))
    except:
        break
        
def postorder(s, e):
    if s > e:
        return
    mid = e + 1                         # 오른쪽 노드가 없을 경우

    for i in range(s+1, e+1):
        if nums[s] < nums[i]:
            mid = i
            break

    postorder(s+1, mid-1)               # 왼쪽 확인
    postorder(mid, e)                   # 오른쪽 확인
    print(nums[s])

postorder(0, len(nums)-1)

1. recursion error가 발생해서 setrecursionlimit를 이용해서 재귀 깊이를 늘려줬다.
2. try~except를 이용해서 입력이 있을 때까지만 입력받음
3. 재귀 이용해서 가장 작은 트리부터 확인
4. for문을 돌려서 루트(nums[s])보다 커지면 오른쪽 노드!
   왼쪽, 오른쪽 나뉘는 부분을 mid로 설정
5. [s+1, mid-1] 왼쪽 노드, [mid, e] 오른쪽 노드로 나누기
   -> 왼쪽 노드들만 다시 확인 (재귀) -> 가장 작은 트리까지!
6. 왼쪽 노드 출력하면 오른쪽 노드 확인하는 함수 확인
   -> 오른쪽 노드 출력
   -> 루트 출력