[백준2263번] 트리의 순회

문제

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

입력

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

출력

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

예제 입력 1

3
1 2 3
1 3 2

예제 출력 1

2 1 3

나의 풀이

중위 순회는 (왼쪽 트리) - 부모 노드 - (오른쪽 트리) 로 나눌 수 있고, 후위 순회는 (왼쪽 트리) - (오른쪽 트리) - 부모 노드 로 나눌 수 있다. 따라서 후위 순회에서 마지막에 나오는 부모 노드의 정보를 가지고 중위 순회에서 왼쪽 트리와 오른쪽 트리를 분리해내는 것이 이 문제의 핵심이었다.

문제를 해결하는 코드에서는 마치 이진탐색과 비슷하게 중위 순회의 시작, 끝, 후위 순회의 시작, 끝의 인덱스를 가지고 재귀를 돌면서 전위 순회를 구현하면 끝이다.

조심해야할 것은 해당 문제는 n이 100,000까지이기 때문에 파이썬의 재귀 제한을 늘려주어야한다.

코드

# 2263번 트리의 순회
import sys
sys.setrecursionlimit(10 ** 6)


def find_pre_order(l_in, r_in, l_post, r_post):
    if l_in > r_in or l_post > r_post:    # 재귀 탈출 조건
        return

    parent = post_order[r_post]
    print(parent, end=' ')

    split_idx = idx[parent]
    left = split_idx - l_in

    # 왼쪽 트리
    find_pre_order(l_in, split_idx - 1, l_post, (l_post + left) - 1)
    # 오른쪽 트리
    find_pre_order(split_idx + 1, r_in, l_post + left, r_post - 1)


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

# 각 노드의 인덱스 번호를 저장
idx = [0] * (n + 1)
for i in range(n):
    idx[in_order[i]] = i

find_pre_order(0, n - 1, 0, n - 1)