[Python] 백준 2263번 트리의 순회

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

2263번: 트리의 순회

문제

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

입력

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

출력

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

코드

import sys
sys.setrecursionlimit(10**6)

n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

nodePosition = [0] * (n + 1) 
for i in range(n):
    nodePosition[inorder[i]] = i

# postorder에서 마지막 원소가 그 트리의 루트 노드인 점을 이용
def preorder(inStart, inEnd, postStart, postEnd):
    if inStart > inEnd or postStart > postEnd:
        return 
    
    root = postorder[postEnd]   # postorder의 마지막 원소가 루트노드
    print(root, end=" ")
    
    left = nodePosition[root] - inStart # 왼쪽 서브트리 노드 수
    right = inEnd - nodePosition[root] # 오른쪽 서브트리 노드 수
    
    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)

그래프를 나누어 재귀적으로 파고들어야한다는 생각은 들었는데 코드를 어떻게 짜야할지 머리가 안 돌아가서 다른 블로그의 글들을 참조했다...뭔가 이진 탐색과 비슷한 느낌이다.

postorder에서는 가장 마지막으로 방문하는 노드가 그 트리의 루트 노드이다. 그러므로 inorder에서 그 노드를 찾는다면 왼쪽 서브트리와 오른쪽 서브트리에 들어가는 노드들을 각각 알 수 있다. 여기서는 왼쪽과 오른쪽 서브트리의 노드 수를 각각 left와 right 변수에 저장하여 인덱스 값으로 사용하여 재귀적으로 파고든다.

 

import sys
sys.setrecursionlimit(10**6)

이 코드를 추가했더니 통과했다.

파이썬의 재귀 최대 깊이의 기본 설정은 1,000회여서 이 코드를 추가하지 않을 경우 런타임 에러가 발생한다. 이 코드는 파이썬의 재귀 최대 깊이를 10**6회로 바꿔준다. 재귀를 이용하여 문제를 풀이할 경우 이 코드를 우선 상단에 쓰는 것을 습관으로 들여야할 것 같다.

트리의 순회

트리의 순회 방법에는 preorder, inorder, postorder 3가지가 있다. 이 세 방법의 차이는 루트 노드를 언제 방문하냐의 차이이다.

1. preorder
   1. 루트 방문
   2. 왼쪽 서브트리 preorder
   3. 오른쪽 서브트리 preorder
2. inorder
   1. 왼쪽 서브트리 inorder
   2. 루트 방문
   3. 오른쪽 서브트리 inorder
3. postorder
   1. 왼쪽 서브트리 postorder
   2. 오른쪽 서브트리 postorder
   3. 루트 방문

graph = [[-1,-1], [2,3],[4,5],[-1,6],[-1,-1],[7,-1],[8,9],[-1,-1],[-1,-1],[-1,-1]]
def preorder(root):
    if root == -1:
        return
    print(root, end=" ")
    preorder(graph[root][0])    # 왼쪽 서브트리
    preorder(graph[root][1])    # 오른쪽 서브트리
    
def inorder(root):
    if root == -1:
        return
    inorder(graph[root][0])     # 왼쪽 서브트리
    print(root, end=" ")
    inorder(graph[root][1])     # 오른쪽 서브트리
    
def postorder(root):
    if root == -1:
        return
    postorder(graph[root][0])   # 왼쪽 서브트리
    postorder(graph[root][1])   # 오른쪽 서브트리
    print(root, end=" ")

print("preorder : ", end="")    
preorder(1)    
print("\ninorder : ", end="")    
inorder(1)    
print("\npostorder : ", end="")    
postorder(1)

 

코드의 그래프는 위의 사진과 같은 그래프이고 preorder, inorder, postorder로 탐색해보면 결과는 다음과 같다.