[백준 4256] 트리 - Python

문제 보기

[사용한 알고리즘]

DFS(깊이 우선 탐색)

 

[문제 접근]

주어진 트리에서 전위 순회와 중위 순회 결과를 적어보니 규칙을 발견하였습니다. 전위 순위에서 발견한 루트 값을 중위 순위에서 찾아보니 루트 값을 기준으로 왼쪽 서브 트리, 오른쪽 서브 트리로 분리되었습니다. 따라서 이를 응용하여 재귀로 구현하면 후위 순위를 구하였습니다.

 

[알고리즘]

1. 전위 순회의 루트와 중위 순회의 값 중 일치하는 인덱스 위치를 찾습니다.

2. 인덱스를 기준으로 왼쪽 서브 트리, 오른쪽 서브 트리를 탐색합니다.

3. 후위 순회이기 때문에 서브 트리 탐색이 끝난 후 루트를 출력합니다.

 

[코드]

import sys


def solve(root, start, end):
    for i in range(start, end):
        if inorder[i] == preorder[root]:
            solve(root + 1, start, i)  # left subtree
            solve(root + i + 1 - start, i + 1, end)  # right subtree
            print(preorder[root], end=" ")


if __name__ == "__main__":
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        preorder = list(map(int, sys.stdin.readline().split()))
        inorder = list(map(int, sys.stdin.readline().split()))
        solve(0, 0, n)
        print("")