백준 2263번: 트리의 순회 (Python)

접근

재귀를 이용하여 문제를 풀 수 있다.

1. 포스트오더의 마지막 숫자는 전체 트리의 루트이다.
2. 인오더의 특성을 이용, 루트를 기준으로 왼쪽트리, 오른쪽트리의 노드 수를 구할 수 있다.
3. 왼쪽 트리의 노드수, 오른쪽 트리의 노드수를 이용하여 인오더를 왼쪽 인오더, 루트, 오른쪽 인오더로 나눌 수 있다.
4. 동일하게 포스트오더를 왼쪽 포스트오더, 오른쪽 포스트오더, 루트로 나눌 수 있다.
5. 왼쪽 포스트오더의 마지막 숫자는 왼쪽 트리의 루트이다... 재귀 반복

위의 연산을 반복해주면서 나오는 루트를 순서대로 저장해주면 프리오더를 얻을 수 있다.

그림으로 보면 조금 더 이해하기 쉽다.

그림으로 그리기 시작할 땐 그림이 훨씬 이해하기 쉬울것 같았는데, 막상 그리고나니 그림을 못그려서 그런지 이해하기 어려운 것 같다. 핵심은 첫번째 분해 연산을 하고, 나누어진 작은 인오더, 포스트오더로 같은 연산을 반복해주면 된다는 것이다.

코드

import sys

sys.setrecursionlimit(10 ** 9)
n = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))
preorder = []
index = [0] * (n + 1)
for i in range(n):
    index[inorder[i]] = i


def preorderset(iStart, iEnd, pStart, pEnd):
    if (iStart > iEnd) or (pStart > pEnd):
        return
    parent = postorder[pEnd]
    preorder.append(parent)
    left = index[parent] - iStart
    right = iEnd - index[parent]

    preorderset(iStart, iStart + left - 1, pStart, pStart + left - 1)
    preorderset(iEnd - right + 1, iEnd, pEnd - right, pEnd - 1)


preorderset(0, n - 1, 0, n - 1)
print(*preorder)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!