[백준][Python] 4256 트리

4256번: 트리

 

코드

import sys

def post(preorder,inorder):
    if len(preorder) == 0:
        return
    elif len(preorder) == 1:
        print(preorder[0], end = ' ')
        return

    r_index = inorder.index(preorder[0])  # 루트노드가 inorder에서 몇 번째에 있는지
    left_in = inorder[0:r_index]
    left_pre = preorder[1:len(left_in)+1]
    post(left_pre,left_in)

    right_in = inorder[r_index+1:]
    right_pre = preorder[len(left_pre)+1:]
    post(right_pre,right_in)
    
    print(preorder[0], end = ' ')

T = int(input())
for _ in range(T):
    n = int(input())
    preorder = list(map(int,sys.stdin.readline().split()))
    inorder = list(map(int,sys.stdin.readline().split()))
    post(preorder,inorder)
    print()

 

설명

전위순회의 가장 첫번째 수는 트리의 루트이다.

중위순회에서 이 루트 번호를 기준으로 왼쪽 트리와 오른쪽 트리로 나뉘게 된다. 이 과정을 왼쪽, 오른쪽 순으로 반복하여 하나의 값만 남았을때 출력하게 되면 후위순회 결과가 나온다.