난이도 : 골드 4
유형 : 트리
https://www.acmicpc.net/problem/5639

문제

전휘 순회한 이진 검색트리의 결과가 주어졌을 때 이를 후위 순회한 결과를 출력하는 문제이다.

이진 검색 트리란?

왼쪽 서브트리에는 작은 값, 오른쪽 서브트리에는 큰 값이 들어간다.

해결 아이디어

전위 순회의 첫 번째 값은 항상 루트 노드이다.
이후의 값들 중 루트보다 작은 값들은 왼쪽 서브트리, 큰 값들은 오른쪽 서브트리를 구성한다.
위 과정을 재귀적으로 반복한다.

해답 및 풀이

import sys
sys.setrecursionlimit(10**6)

preorder = [] # 전위순회 input값을 담을 리스트

# 입력의 개수가 정해지지 않았기에 EOF(입력 종료)까지 계속 읽는다.
while True:
    try:
        preorder.append(int(sys.stdin.readline())) 
    except:
        break

def postorder(start, end): # 후위 순회
    if start > end:
        return

    root = preorder[start] # 루트노드는 전위 순회에 start값
    divide = end + 1  # devide는 왼쪽 서브트리와 오른쪽 서브트리를 나누는 경계선 인덱스, 일단 오른쪽 없음이라고 가정

    for i in range(start + 1, end + 1):
        if preorder[i] > root: # 루트 노드보다 큰놈을 찾자마자 개를 divide로 지정해주고 탈출
            divide = i
            break
# 이 후위순회 함수는 좌-우-루트 를 프린트해야하니까 재귀적으로 좌 후위순회 호출, 우 후위순회 호출, 루트 출력 이렇게 이루어져 있다.
    postorder(start + 1, divide - 1)  # 왼쪽 서브트리 후위 순회
    postorder(divide, end)           # 오른쪽 서브트리 후위 순회
    print(root)

postorder(0, len(preorder) - 1)