[백준 4256] 트리 (python)

4256번: 트리

---

 

분할 정복 문제이다. 트리를 왼쪽 오른쪽 쪼개서 계산해주면 된다.

preorder:  3 6 5 4 8 7 1 2

inorder:   5 6 8 4 3 1 2 7

postorder:  5 8 4 6 2 1 7 3

preorder에 첫번째 있는 값(3)이 해당 트리에 root가 되고 root를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 분할해 다시 계산해준다.

 

1. preorder이 없다면 pass
2. 1개 라면 result에 저장해준다.
3. 왼쪽 서브트리와 오른쪽 서브트리를 계산해준 후, root값을 마지막에 출력해준다.

 

import sys
input = sys.stdin.readline


def postorder(preorder, inorder):
    if len(preorder) == 0:
        return
    if len(preorder) == 1:
        result.extend(preorder)
        return
        
    root = preorder[0]
    inorderidx = inorder.index(root)
    
    postorder(preorder[1:inorderidx+1], inorder[:inorderidx])
    postorder(preorder[inorderidx+1:], inorder[inorderidx+1:])
    result.append(root)


T = int(input())
for _ in range(T):
    result = []
    N = int(input())
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))
    postorder(preorder, inorder)
    print(*result)