Category
알고리즘  자료구조

[4256] 트리

by Hwang

문제

https://www.acmicpc.net/problem/4256

풀이

전위 순회의 결과로 이진 트리의 탐색 순서를 알 수 있고, 중위 순회의 결과로 노드간의 위치 관계를 알 수 있습니다.

이 두 가지 정보를 이용해서 후위 순회를 진행해줬습니다.

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    preorder = list(map(int, sys.stdin.readline().strip().split()))
    inorder = list(map(int, sys.stdin.readline().strip().split()))
    inorder_index = dict()
    for i in range(N):
        inorder_index[inorder[i]] = i
    index = 0

    def postorder(right):
        global index
        c_index = index
        index += 1
        if index < N and inorder_index[preorder[c_index]] > inorder_index[preorder[index]]:
            postorder(inorder_index[preorder[c_index]])
        if index < N and inorder_index[preorder[c_index]] < inorder_index[preorder[index]]:
            if right > inorder_index[preorder[index]]:
                postorder(right)
        print(preorder[c_index], end=' ')
    postorder(N)
    print()


 Comment