[Python] 백준 2263 - 트리의 순회 문제 풀이

Overview

BOJ 2263번 트리의 순회 문제 Python 풀이
분류: Tree (트리)

---

문제 페이지

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

---

풀이 코드

from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
input = lambda: stdin.readline().rstrip()


def get_preorder(in_start: int, in_end: int, post_start: int, post_end: int) -> None:
    if in_start >= in_end or post_start >= post_end:
        return

    preorder.append(postorder[post_end - 1])
    root = indices[preorder[-1]]

    get_preorder(in_start, root, post_start, post_start + root - in_start)
    get_preorder(root + 1, in_end, post_start + root - in_start, post_end - 1)


if __name__ == "__main__":
    n = int(input())
    inorder = list(map(int, input().split()))
    postorder = list(map(int, input().split()))

    preorder = []
    indices = {inorder[i]: i for i in range(n)}
    get_preorder(0, n, 0, n)
    print(' '.join(map(str, preorder)))


"""
트리 순회 문제
함수 인자로 리스트가 아닌 인덱스를 전달하여 메모리를 줄여야함
get_preorder(inorder: List[int], postorder: List[int])
->
get_preorder(in_start: int, in_end: int, post_start: int, post_end: int)
"""

트리의 inorder와 postorder를 통해 preorder를 구해야 한다. 매 단계에서 부모 노드를 구하고 왼쪽 서브트리와 오른쪽 서브트리를 재귀적인 방식으로 반복한다.
위 코드에서 주의할 점은 get_preorder 함수의 인자를 전달 할 때, 리스트를 전달하면 메모리 초과가 발생한다는 것이다. 따라서 inorder, postorder의 서브 리스트가 아닌 시작 인덱스와 끝 인덱스를 인자로 전달하며 풀이해야한다.