문제 설명

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력 조건

첫째 줄에 프리오더를 출력한다.

전체 코드 (꼭 복습하자.)

import sys

sys.setrecursionlimit(10 ** 5)

n = int(sys.stdin.readline().rstrip())
in_order = list(map(int, sys.stdin.readline().rstrip().split()))
post_order = list(map(int, sys.stdin.readline().rstrip().split()))

pre_order = []

tree_dict = dict()
for i in range(len(in_order)):
    tree_dict[in_order[i]] = i


# 후위 탐색의 경우 절반으로 분할하게 되면, 구간의 마지막 값이 해당 구간의 루트 노드이다.
# 따라서 후위 탐색 결과를 이용해 먼저 해당 구간의 루트노드를 구한 후,
# 중위 순회 결과를 참고해 해당 구간 왼쪽을 왼쪽 자식으로, 해당 구간 오른쪽을 오른쪽 자식으로 구분한다.
def recursion(in_start: int, in_end: int, post_start: int, post_end: int):
    # 범위를 벗어나면 기저 조건에 도달하여 종료한다.
    if in_start > in_end or post_start > post_end:
        return
    else:
        # 루트 노드 먼저 출력
        print(post_order[post_end], end=' ')
        # 루트노드의 인덱스를 중위 순회결과로부터 얻는다.
        index = tree_dict[post_order[post_end]]

        # 중위 순회를 기준으로 왼쪽, 오른쪽을 나눈다.
        # 그러면 왼쪽 서브트리의 노드 개수와 오른쪽 서브트리의 개수를 알 수 있다.
        left = index - in_start
        right = in_end - index

        # 중위 순회의 경우 왼쪽 서브트리의 범위는 (시작 인덱스 ~ 시작 인덱스 + 왼쪽 서브트리 노드 개수 -1),
        # 후위 순회의 경우 왼쪽 서브트리의 범위는 (시작 인덱스 ~ 시작 인덱스 + 왼쪽 서브트리 노드 개수 -1)
        recursion(in_start, in_start + left - 1, post_start, post_start + left - 1)

        # 중위 순회의 경우 오른쪽 서브트리의 범위는 (끝 인덱스 ~ 오른쪽 노드 개수 +1 ~ 끝 인덱스),
        # 후위 순회의 경우 (끝 인덱스 - 오른쪽 노드 개수 ~ 끝 인덱스 -1 )의 관계를 재귀적으로 만족한다.
        recursion(in_end - right + 1, in_end, post_end - right, post_end - 1)


recursion(0, len(in_order) - 1, 0, len(post_order) - 1)