골드2

문제 2263

해당 문제 링크

정답

## 트리의 순회

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

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

def preorder(inStart, inEnd, postStart, postEnd):
    if (inStart > inEnd) or (postStart > postEnd):
        return
    
    root = postorder[postEnd]
    
    leftNode = nodeNum[root] - inStart
    rightNode = inEnd - nodeNum[root]
    
    print(root, end = " ")
    preorder(inStart, inStart + leftNode - 1, postStart, postStart + leftNode - 1)
    preorder(inEnd - rightNode + 1, inEnd, postEnd - rightNode, postEnd - 1)

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

풀이

중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6
후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0

후위 순회의 맨 마지막 원소 = 최상위 루트
이를 기준으로 중위 순회를 나누면, 왼쪽은 왼쪽 서브 트리, 오른쪽은 오른쪽 서브 트리임을 알 수 있다.

중위 순회 : 7 3 8 1 9 4 10 (왼쪽 서브 트리) / 0 (최상위 루트) / 11 5 2 6 (오른쪽 서브 트리)
후위 순회 : 7 8 3 9 10 4 1 (왼쪽 서브 트리) / 11 5 6 2 (오른쪽 서브 트리) / 0 (최상위 루트)

중위 순회에서 왼쪽 서브 트리의 범위는

시작 인덱스 ~ (시작 인덱스 + 왼쪽 서브 트리의 노드 수 - 1)
ex) 0 ~ (0+7-1) = 0 ~ 6

중위 순회에서 오른쪽 서브 트리의 범위는

(끝 인덱스 - 오른쪽 서브 트리의 수 + 1) ~ 끝 인덱스
ex) (11-4+1) ~ 11 = 8 ~ 11

후위 순회에서 왼쪽 서브 트리의 범위는

시작 인덱스 ~ (시작 인덱스 + 왼쪽 서브 트리의 노드 수 - 1)
ex) 0 ~ (0+7-1) = 0 ~ 6

후위 순회에서 오른쪽 서브 트리의 범위는

(끝 인덱스 - 오른쪽 서브 트리의 수) ~ (끝 인덱스 - 1)
ex) (11-4) ~ (11-1) = 7 ~ 10

직접 손으로 써보면 이해가 쉽게 된다
참고 코드 설명