[Python] 백준 4256 - 트리

Overview

BOJ 4256번 트리 Python 문제 풀이
분류: Divide and conquer (분할정복)

---

문제 페이지

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

---

풀이 코드

from sys import stdin
from typing import List


def get_postorder(preorder: List[int], inorder: List[int]):
    if not inorder:
        return
    node = preorder.pop(0)
    idx = inorder.index(node)
    get_postorder(preorder, inorder[:idx])
    get_postorder(preorder, inorder[idx + 1:])
    print(node, end=' ')


def main():
    def input():
        return stdin.readline().rstrip()

    t = int(input())
    for _ in range(t):
        n = int(input())
        preorder = list(map(int, input().split()))
        inorder = list(map(int, input().split()))

        get_postorder(preorder, inorder)
        print()


if __name__ == "__main__":
    main()

루트 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리를 재귀적으로 탐색하고, 현재 루트 노드의 값을 출력하여 postorder 탐색을 진행한다. 재귀적으로 탐색할 때에는 preorder 리스트와 inorder 리스트를 각각 왼쪽 서브 트리와 오른쪽 서브 트리 영역으로 나누어 진행한다.

재귀함수에서 preorder의 맨 앞 원소는 항상 현재 트리의 루트 값이다. 따라서 preorder의 첫 번째 값을 pop하여 제거하고, 왼쪽과 오른쪽 서브 트리에 대하여 재귀적으로 탐색한 뒤, pop 했던 값을 출력한다.
inorder는 preorder 첫 번째 원소가 위치한 인덱스를 기준으로 반으로 나누어, 왼쪽과 오른쪽 서브 트리에 대하여 재귀적으로 탐색한다.