이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
import sys
sys.setrecursionlimit(10**9)
def post_order(s, e):
if s >= e:
return
root = pre_order[s]
idx = s+1
for i in range(s+1, e):
if pre_order[i] > root:
idx = i
break
post_order(s+1, idx)
post_order(idx, e)
print(root)
return
pre_order = []
while 1:
try:
pre_order.append(int(sys.stdin.readline()))
except:
break
post_order(0, len(pre_order))