백준 2263 트리의 순회 - 파이썬

풀이.

다음과 같은 트리가 있다하면

순회의 결과는 다음과 같다.

전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6

 

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

 

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

 

중위와 후위를 살펴보면, 후위의 마지막 요소가 루트 노드인 것을 알 수 있다.

그러면 중위 순회에서 루트 노드를 기준으로 left, right를 나누면

(7, 3, 8, 1, 9, 4, 10), (11, 5, 2 6)으로 나뉘어진다.

이 left, right의 길이만큼 후위 순회에서 나눈다면

(7, 8, 3, 9, 10, 4 ,1), (11, 5, 6, 2) 로 나뉘어진다

다시 후위 순회와 중위 순회를 살펴보면 해당 후위 순회의 마지막 요소가 루트 노드인 것을 살펴볼 수 있다.

이 과정들을 반복해서 root들을 떼어내서 전위 순회로 만들면 된다.

 

소스코드.

import sys

def order(in_left, in_right, post_left, post_right):
    if(in_left > in_right) or (post_left > post_right):
        return

    root = postorder[post_right]
    preorder.append(root)

    left = location[root] - in_left
    right = in_right - location[root]

    order(in_left, in_left + left -1, post_left, post_left + left - 1) # 왼쪽 노드
    order(in_right - right + 1, in_right, post_right - right, post_right - 1) # 오른쪽 노드

input = sys.stdin.readline
sys.setrecursionlimit(10**6)
preorder = []
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
location = [0] * (n+1)
for i in range(n):
    location[inorder[i]] = i
order(0, n-1, 0, n-1)
print(*preorder)