[백준] 5639 이진검색트리 in Python : tree 전위순회의 특성을 이용한 풀이 + EOF를 이용해서 입력받기

try except 문은 이럴때 사용한다 !! 라는 것을 알게되었다. 

보통 입력값 갯수가 주어지는데 이문제에서는 안주어져서 어떻게 하나 싶었는데 파이썬에서는 EOF 에러를 잡을 수 있는 구문이 바로 except! 

except를 이용해서 예외적으로 오류를 처리할 수 있게 해준다. 

그리고 풀이는 전위순회의 특성을 이용해서 풀었다 

전위순회는 root -> left subtree -> right subtree 순서대로 순회한다. 즉, 

1) root는 array[0] # 맨 앞의 원소가 루트노드

2) array를 쭉 확인하다가 처음으로 root보다 큰 값이 나오면 이것이 바로 right subtree의 첫번째 원소가 되므로, left와 right 서브트리의 경계값이 된다 

이 두가지를 이용하여 postorder 함수를 구성하면 된다. 

 

# 5639 이진 검색 트리
import sys
sys.setrecursionlimit(10**6)
tree = []


def postorder(start, end):
    if start > end:
        return
    root = tree[start]
    idx = end+1

    for i in range(start+1, end+1):
        if root < tree[i]:
            idx = i # left sub tree 와 right subtree의 경계가 되는 index    
            break
    postorder(start+1, idx-1)
    postorder(idx, end)
    print(root)

while True:
    try:
        tree.append(int(input()))
    except: # EOF 입력되면 에러가 일어나는것을 이용
        break

postorder(0, len(tree)-1)