[백준/Python] 4256. 트리

4256. 트리

4256번: 트리

• 트리
• 분할 정복

트리는 분할 가능한(큰 것을 작은 것으로 쪼갤 수 있는) 자료구조에 해당

따라서 트리의 탐색은 재귀+분할정복으로 이루어질 수 있다.

전체 트리의 루트는 3이지만, 루트 3을 기준으로 왼쪽/오른쪽으로 트리를 나누면
루트가 6, 7인 두 개의 subtree가 생긴다.

트리의 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)가 갖는 의미

• 전위 순회는 root, left child, right child 순으로 순회한다.
• 중위 순회는 left child, root, right child 순으로 순회한다.
• 후위 순회는 left child, right child, root 순으로 순회한다.
• 따라서 중위 순회와 다른 한 가지 순회의 결과가 주어졌을 때, 분할정복을 이용하면 나머지 한 가지 순회의 결과도 얻어낼 수 있다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(15000)

def get_postorder(preorder, inorder, postorder):
    if len(preorder) == 0:
        return
    root = preorder[0]
    index = inorder.index(root)
    left_inorder = inorder[:index]
    right_inorder = inorder[index+1:]
    left_preorder = preorder[1:len(left_inorder)+1]
    right_preorder = preorder[len(left_inorder)+1:]
    get_postorder(left_preorder, left_inorder, postorder)
    get_postorder(right_preorder, right_inorder, postorder)
    postorder.append(root)

for i in range(int(input())):
    n = int(input())
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))
    postorder = []
    get_postorder(preorder, inorder, postorder)
    print(' '.join(map(str, postorder)))