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

---

문제

노드의 개수,
중위 순회 와 후위 순회가 주어졌을 때
전위 순회를 어떻게 할 지 출력하는 문제.

---

이진 트리는 (전위 + 중위), (중위 + 후위) 순회 결과로 트리를 구성할 수 있다고 한다.

핵심 아이디어

후위 순회의 마지막 원소는 루트 노드이다.
중위 순회에서 그 루트를 기준으로 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리이다.
이 정보를 재귀적으로 반복하면 트리 전체를 만들 수 있다.

---

중위 순회에서 각 값의 인덱스를 빠르게 찾기 위해 딕셔너리로 만든다.

in_order = [4, 2, 5, 1, 6, 3, 7] 라면

in_idx는

in_idx = {
    4: 0,
    2: 1,
    5: 2,
    1: 3,
    6: 4,
    3: 5,
    7: 6
} 

가 된다.

enumerate(in_order)는
(0, 4), (1, 2), (2, 5), (3, 1) 이렇게 순서쌍들을 만들어준다.

해답 및 풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

# 중위 순회에서 각 값의 인덱스를 빠르게 찾기 위한 딕셔너리
in_idx = {value: idx for idx, value in enumerate(in_order)}

def build_preorder(in_start, in_end, post_start, post_end): # 중위, 후위 순회의 시작, 끝 인덱스
    if in_start > in_end or post_start > post_end:
        return

    # 후위 순회의 마지막 값이 루트
    root = post_order[post_end]
    print(root, end=' ')

    # 루트의 중위 순회 위치
    root_idx = in_idx[root]
    # 왼쪽 서브트리 크기
    left_size = root_idx - in_start

    # 왼쪽 서브트리 재귀
    build_preorder(in_start, root_idx - 1, post_start, post_start + left_size - 1)
    # 오른쪽 서브트리 재귀
    build_preorder(root_idx + 1, in_end, post_start + left_size, post_end - 1)

# 전체 범위로 시작
build_preorder(0, n - 1, 0, n - 1)

인자를 네개 받는 이유는 트리의 일부분(서브트리)를 중위/후위 순회 배열에서 정확히 자르기 위해 시작과 끝 인덱스를 각각 2개씩 — 총 4개를 받는 것이다.