Baekjoon 2263. 트리의 순회 / Python

2263. 트리의 순회

난이도 : 골드 1
소요 시간 : 10분
날짜 : 2024.12.30
언어 : 파이썬
알고리즘 유형 : 재귀, 트리, 분할 정복

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 트리의 크기 n이 주어짐
2. 중위순회(inorder)와 후위순회(postorder)가 주어짐
3. 전위순회(preorder)결과를 구하기.

2. 해결 방식

1. 중위순회는 왼쪽부터 하위트리를 우선으로 트리를 방문 후 루트를 방문하는 방식
2. 후위순회는 왼쪽부터 "하위트리를 모두 방문한 후" 루트를 방문하는 방식
3. 전위순회는 루트노드부터 시작하여 왼쪽 자식먼저 방문하는 방식

1. 재귀함수의 원리 및 사용
   • 후위순회의 마지막 요소는 현재 서브트리의 루트 노드이다.
   • 중위순회에서의 루트를 기준으로 왼쪽, 오른쪽으로 서브트리를 나눈다.
   • 루트 노드를 출력한다.(전위순회)

3. 정답 코드

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**5)

n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

tree = [0] * (n + 1)
for i in range(n):tree[inorder[i]] = i

def preorder(in_s, in_e, po_s, po_e):
    if in_s > in_e or po_s > po_e:return
    parent = postorder[po_e]
    print(parent, end = " ")

    left, right = tree[parent] - in_s, in_e - tree[parent]
    preorder(in_s, in_s + left - 1, po_s, po_s + left - 1)
    preorder(in_e - right + 1, in_e, po_e - right, po_e - 1)

preorder(0, n - 1, 0, n - 1)