[Python/파이썬] 백준 2263번: 트리의 순회

문제

 

풀이

중위 순회 : 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)

 

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

(끝 인덱스 - 오른쪽 서브 트리의 수 + 1) ~ 끝 인덱스

 

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

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

 

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

(끝 인덱스 - 오른쪽 서브 트리의 수) ~ (끝 인덱스 - 1)

코드

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()))

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)

마무리

이전에 풀었던 이진 검색 트리(백준 :5639)와 비슷해서 비교적 쉽게 풀었다.