[골드 1] 백준 2263 - 트리의 순회 (파이썬)

https://www.acmicpc.net/problem/2263

풀이

트리 재구성 및 전위 순회 출력을 하는 문제이다.

문제는 중위 순회와 후위 순회 결과를 통해 전위 순회 결과를 구하는 것이다.

• 입력
  • 첫 줄 : 노드 개수 N
  • 둘째 줄 : 중위 순회 결과 INORDER
  • 셋째 줄 : 후위 순회 결과 POSTORDER
• 출력
  • 전위 순회 결과

순회 정의

전위(preorder)	Root → Left → Right
중위(inorder)	Left → Root → Right
후위(postorder)	Left → Right → Root

1. 후위 순회의 마지막 원소는 항상 현재 서브트리의 루트 노드이다.
2. 루트 값을 중위 순회에서 찾아 좌/우 서브트리의 범위를 나눈다.
3. 나뉜 범위를 이용해 재귀적으로 좌/우 서브트리를 계속 분할한다.
4. 루트를 먼저 출력하므로 전위 순회가 된다.

코드

# 백준 2263 - 트리의 순회
# 분류 : 트리

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

N = int(input())
INORDER = list(map(int, input().split()))
POSTORDER = list(map(int, input().split()))

INDEX = {val : idx for idx, val in enumerate(INORDER)}

def build(in_start, in_end, post_start, post_end) :
    if in_start > in_end or post_start > post_end :
        return

    root = POSTORDER[post_end]
    print(root, end = ' ')
    root_index = INDEX[root]
    left_size = root_index - in_start

    build(in_start, root_index - 1, post_start, post_start + left_size - 1)
    build(root_index + 1, in_end, post_start + left_size, post_end - 1)

build(0, N - 1, 0, N - 1)