[트리/Python] 2263번: 트리의 순회- 효과는 굉장했다!

2263번: 트리의 순회

 

알고리즘 분류

• 트리
• 분할 정복
• 재귀

 

 

SOLUTION

import sys
sys.setrecursionlimit(10**6)

def preorder(inorder_start, inorder_end, postorder_start, postorder_end):
    if inorder_start > inorder_end  or postorder_start > postorder_end:
        return
    
    # 루트
    root = postorder[postorder_end]
    
    # 전위 순회 : 루트 -> 왼쪽 -> 오른쪽
    print(root, end=" ")
    
    left = position[root] - inorder_start 
    right = inorder_end - position[root] 
    
    # 왼쪽 서브 트리
    preorder(inorder_start, inorder_start+left-1, postorder_start, postorder_start+left-1)
    # 오른쪽 서브 트리
    preorder(inorder_end-right+1, inorder_end, postorder_end-right, postorder_end-1)


n = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))
# 중위 순회의 탐색 인덱스 순서
position = [0] * (n+1)
for i in range(n):
    position[inorder[i]] = i
    
preorder(0, n-1, 0, n-1)