백준 5639 이진 검색 트리 / python

1. 입력으로 전위 순회한 결과가 주어진다.
2. 입력값의 개수가 주어져 있지 않다.
3. 노드의 수가 정확하게 주어져 있지 않음 (10000이하) 따라서, 입력 받는 방법도 중요
4. 루트/왼/오 로 되어 있는 것을 > 왼/오/루트 로 출력.

• preorder = [] 전위 순회한 결과를 담기위한 그릇.
• while, try~ except 문을 통해 입력값이 들어올 때 까지 입력받음.

function : postorder(start, end)

• 배열의 인덱스를 돌며 후위 순회 진행
• root = preorder [ start ]
  -> 루트노드로 설정
• 배열을 돌며 오른자식 노드의 위치(idx)를 찾는다.
• start = start + 1, end = idx // start = idx, end = end
• 새롭게 두 part 로 나눠서 재귀함수 호출.
• print(root) >> 후위 순회이므로 보내고 나서 루트노드 출력.
• if start>= end : return 배열을 모두 돌면 return

import sys

sys.setrecursionlimit(10 ** 6)

preorder = []


def postorder(start, end):
    if start >= end:
        return
    root = preorder[start]

    if preorder[end - 1] <= root:
        postorder(start + 1, end)
        print(root)
        return

    idx = 0
    for i in range(start + 1, end):
        if preorder[i] > root:
            idx = i
            break
    postorder(start + 1, idx)
    postorder(idx, end)
    print(root)


while True:
    try:
        preorder.append(int(sys.stdin.readline()))
    except:
        break

postorder(0, len(preorder))