⚠️ 문제
https://www.acmicpc.net/problem/5639
🔐 풀이
트리를 전위 순회한 결과를 입력으로 주는데, 전위 순회는 루트-왼쪽-오른쪽 순으로 탐색하기 때문에
루트 출력 -> 왼쪽 서브트리 모두 출력 -> 오른쪽 서브트리 모두 출력 형태가 됩니다.
문제에서는 후위 순회한 결과를 출력해야하기 때문에 아래처럼 재귀를 통해 왼쪽 서브트리를 먼저 끝까지 탐색하고 오른쪽 서브트리를 끝까지 탐색하고 루트를 출력해주면 됩니다.
🧑🏻💻 코드
import sys
sys.setrecursionlimit(10**9)
preorder_arr = []
# 엔터 들어올 때까지 입력
while True:
try:
preorder_arr.append(int(sys.stdin.readline().rstrip()))
except:
break
def postorder(root_idx, end_idx):
if root_idx > end_idx:
return
global preorder_arr
# 만약 root보다 큰 값 없는 경우 전부 왼쪽 서브트리로 취급
right_start = end_idx + 1
for i in range(root_idx + 1, end_idx + 1):
if preorder_arr[root_idx] < preorder_arr[i]:
right_start = i
break
# root 다음부터 왼쪽 서브트리 탐색
postorder(root_idx + 1, right_start - 1)
# 왼쪽 서브트리 탐색 끝나면 오른쪽 서브트리 탐색
postorder(right_start, end_idx)
# 왼쪽, 오른쪽 서브트리 탐색 끝나면 root 출력
print(preorder_arr[root_idx])
postorder(0, len(preorder_arr) - 1)