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

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

5639번: 이진 검색 트리

 

문제 해결

전위 순회(preorder)한 노드의 value 값을 리스트 안에 차례대로 받는다.

인덱스를 차례대로 키워가며 노드의 value 값이 이전보다 작으면 깊이를 늘리지 않고 오른쪽 자식 값으로 가는 규칙이 있다.

이 트리를 후위 순회(postorder)한 결과를 출력하는 것이 문제

인덱스를 이용하여 후위 순회 함수를 만들면 된다.

중간에 노드의 value 값이 이전보다 작아 더 깊이 들어가는 것이 아닌 오른쪽 자식으로 가는 index를 mid로 잡고 후위 순회 함수를 만들면 된다.

 

CODE

import sys
sys.setrecursionlimit(100000)
tree = []
que = []
while True:
    try:
        que.append(int(input()))
    except EOFError:
        break

def postorder(first,end):
    if first>end:
        return
    mid = end + 1 # 루트보다 큰 값이 존재하지 않을 경우 대비
    for i in range(first+1,end+1):
        if que[first] < que[i]: # 오른쪽 리프에 생겨야하는 i
            mid = i
            break
    postorder(first+1, mid-1)
    postorder(mid,end)
    print(que[first])
postorder(0,len(que)-1)