[트리의 순회/G1/Python3]

2263번 트리의 순회 G1

 

문제
n개의 정점을 갖는 이진트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력
첫째 줄에 프리오더를 출력한다.

트리, 분할 정복, 재귀

 

프리오더, 전위 순회 : Root, Left, Right 순서이다.

인오더, 중위 순회 : Left, Root, Right 순서이다.

포스트오더, 후위 순회 : Left Right Root 순서이다.

 

후위 순회의 경우 항상 root가 마지막에 들어가게 된다.

이를 이용해서 재귀, 분할정복 방식으로 풀이하였다.

 

dfs에는 4가지 인자가 들어가는데, 탐색 영역 s, e와 포스트오더 영역 ps, pe로 구성되어 있다.

전위 순회를 출력해야 하기 때문에, root 먼저 출력하고 좌우를 나누었다.

 

리스트로 인오더의 값을 인덱스로 변환하여 O(1)에 검색할 수 있도록 만들었다.

 

 

 

import sys
sys.setrecursionlimit(10**6)

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

inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))

get_index_inorder = {}

for i in range(n):
    get_index_inorder[inorder[i]] = i

def find(i, j, ps, pe):
    if i>j or ps>pe: return
    
    root = postorder[pe]
    index = get_index_inorder[root]
    
    print(root, end=' ')
    
    find(i, index-1, ps, ps+index-1-i)
    find(index+1, j, pe-j+index, pe-1)


find(0, n-1, 0, n-1)​

 

---

 

트리의 이해도를 확인할 수 있는 문제이다.