[BAEKJOON]2263 트리의 순회- Python

문제 요약

• 알고리즘 분류: 트리
• 난이도: Gold2
• 문제내용:
  • Inorder, Postorder 주어질때 preeorder을 구해라
• 사이트: https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

문제풀이

   이번에는 문제 유형은 트리 탐색에 관련 문제이다. 트리에 관한 자세한 내용은 여기에서 보면된다.

문제 접근방법

 inorder과 postorder만 주어질때 preeorder로 구현할려니까 막상 막히는 경우가 많다. 이번 문제는 트리의 탐색에 대해서 정확하게 알아야 풀수가 있다.

일단 위에 그림을 보면 트리와 각 탐색순서가 보일 것이다. 루트 1기준으로 봤을때 루트는 빨간색 왼쪽 자식 노드들은 주황색 오른쪽 자식 노드는 초록색으로 되어 있다. Inorder과 PostOrder을 보면 앞에는 주황색 뒤에는 초록색이 보일것이다. 그리고 post order을 보면 루트노드가 맨 뒤에 있다는 것을 확인 할수가 있다. 다시 Inorder과 PostOrder를 표를 보면 아래와 같이 확인을 할수 있다.

• InOrder: 왼쪽 - 루트 - 오른쪽
• PostOrder: 왼쪽 - 오른쪽 - 루트
• PreOrder:  루트 - 왼쪽 - 오른쪽

위에 방식에 따라면 처음에 postorder를 맨 뒤가 루트노드라서 postorder 배열의 맨 뒤에 preorder에 추가하고 inorder배열에서 루트노드 기준으로 왼쪽 노드 개수를 파악해서 그 개수 만큼 postoder 배열를을 인덱스 슬라이싱 해서 왼쪽, 오른쪽을 나눈 다음 왼쪽 부터 탐색해서 왼쪽 배열의 맨뒤에 postorder를 추가하는 작업을 반복하면된다. 그러면 우리가 알아야 되는 것은 postOrder의 시작과 끝, inorder의 시작과 끝 인덱스의 위치를 알아야 한다. 그

예제

위 그림의 예제를 하겠다.

inorder: 8 4 9 2 5 1 6 3 7

postorder: 8 9 4 5 2 6 7 3 1

preorder: 1

 처음에 postorder의 맨 뒤를 preorder에 저장한다. 그 다음 루트노드 1기준으로 inorder에서 왼쪽 자식 개수만큼 postorder를 자른다.

inorder: 8 4 9 2 5

postorder: 8 9 4 5 2

preorder: 1 2

 여기서 루트노드는 2이다 그러면 노드 2 기준으로 오른쪽 왼쪽을 자른다.

inorder: 8 4 9

postorder: 8 9 4

preorder: 1 2 4

 루트노드는 4이다. 여기서 또 4기준으로 오른쪽 왼쪽을 자른다.

inorder: 8 / 9

postorder: 8 / 9

preorder: 1 2 4 8 9

 자르면 8밑으로는 자식이 없어서 다시 4로 돌아간 다음 오른쪽 노드를 탐색한다. 그러면 9인데 자식이없다. 그러면 다시 부모로 돌아가고 노드 4에서는 자식 노드 탐색 했기 때문에 다시 부모 노드 2로 올라간다.

inorder: 5

postorder: 5

preorder: 1 2 4 8 9 5

 노드 2에서 오른쪽 탐색하면 5인데 5밑으로 가면 없기 때문에 부모노드로 돌아가고 노드 2의 탐색이 끝났기 때문에 루트 노드로 돌아가서 오른쪽을 탐색한다.

inorder: 6 3 7

postorder: 6 7 3

preorder: 1 2 4 8 9 5 3

루트 노드에서 오른쪽 노드를 보면 루트 노드는 3이다. 그 다음에는 6 7만 남아있고 왼쪽 노드 탐색한것 처럼 오른쪽도 탐색하면 결과가 1 2 4 8 9 5 3 6 7이 나온다.

 

정리

1. postorder에서 맨 뒤가 루트 노드이다.
2. inorder에서 왼쪽 오른쪽 노드의 개수를 파악해서 postorder를 왼쪽 오른쪽을 나눈다.
3. 루트 노드 기준으로 왼쪽 자식 노드 -> 오른쪽 자식 노드순으로 분할해서 재귀 탐색으로 한다.

Code

Python

import sys
sys.setrecursionlimit(10**9)

def order(in_start, in_end, post_start, post_end):
    rootnode = postorder[post_end]
    root_index = location[rootnode]
    left_size = root_index - in_start
    
    if in_start > in_end or post_start > post_end:
        return
    
    preorder.append(rootnode)
    # 왼쪽 자식 노드 탐색
    order(in_start, root_index - 1, post_start, post_start + left_size - 1 )
    # 오른쪽 자식 노드 탐색
    order(root_index + 1, in_end, post_start + left_size, post_end - 1)
    
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
location = [0] * (n + 1)
for i in range(n):
    location[inorder[i]] = i
preorder = []
order(0, n - 1, 0, n - 1)
print(' '.join(map(str, preorder)))