[ 백준 ][ 골드2 ] 2263번 - 트리의 순회 ( 파이썬 Python3 )

링크 : https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

코드

---

import sys
sys.setrecursionlimit(10**6)

n = int(input())
inOrder, postOrder = list(map(int,input().split())), list(map(int,input().split()))

arr = [0] * (n+1)
for i in range(n):
    arr[inOrder[i]] = i

def preOrder(inStart,inEnd,postStart,postEnd):
    if inStart > inEnd  or postStart > postEnd:
        return

    root = postOrder[postEnd]

    left = arr[root] - inStart
    right = inEnd - arr[root]

    print(root, end = " ")
    preOrder(inStart,inStart+left-1,postStart,postStart+left-1)
    preOrder(inEnd-right+1,inEnd,postEnd-right,postEnd-1)

preOrder(0,n-1,0,n-1)

 

풀이

---

오래전부터 풀어보려고 시도하다가 이상하게 너무 풀기 싫어서 미뤄두던 문제인데 드디어 내가 스스로 해결하진 않았지만 풀이법을 이해해버렸다.

 

전위, 중위, 후위 순회의 트리 탐색 순서는 다음과 같다.

• 전위 순회 : 루트 -> 왼쪽 -> 오른쪽
• 중위 순회 : 왼쪽 -> 루트 -> 오른쪽
• 후위 순회 : 왼쪽 -> 오른쪽 -> 루트

우리가 전위 순회를 출력하기 위해서는 '루트'를 찾아야 한다.

 

전위 순회는 루트 -> 왼쪽 서브트리의 루트 -> 오른쪽 서브트리의 루트 순으로 탐색하므로 중위 순회와 후위 순회를 이용하여 왼쪽 서브트리와 오른쪽 서브트리를 나누고 나눌 때마다 기준이 되는 루트를 출력하면 된다.

 

위의 순서들에서 루트를 보게 되면 후위 순회는 루트가 가장 마지막인 반면 중위 순회는 가운데에 루트가 있다. 다시 말하면 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리가 나뉘게 된다.

 

중위 순회 -> 7 3 8 1 9 4 10 0 11 5 2 6

후위 순회 -> 7 8 3 9 10 4 1 11 5 6 2 0

 

• 중위 순회에서 왼쪽 서브트리의 범위 : 시작 인덱스 ~ (시작 인덱스 + 왼쪽 서브 트리의 노드 수 - 1)
• 중위 순회에서 오른쪽 서브트리의 범위 : (끝 인덱스 - 오른쪽 서브 트리의 수 + 1) ~ 끝 인덱스
• 후위 순회에서 왼쪽 서브 트리의 범위 : 시작 인덱스 ~ (시작 인덱스 + 왼쪽 서브 트리의 노드 수 - 1)
• 후위 순회에서 오른쪽 서브 트리의 범위: (끝 인덱스 - 오른쪽 서브 트리의 수) ~ (끝 인덱스 - 1)

따라서 현재 트리의 루트를 기준으로 왼쪽 서브 트리와 오른쪽 서브 트리를 나눠서 재귀적으로 루트노트를 출력하면 된다.

 

참고 블로그 : https://ku-hug.tistory.com/135