18. 백준 5639 (골드4) : 이진검색트리 _ python풀이 / 이진트리

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

50
30
24
5
28
45
98
52
60

예제 출력 1 복사

5
28
24
45
30
60
52
98
50

---

*문제 해석

전위 순회로 입력이 주어진다. [0]위치에 있는 것은 루트 노드이고, 왼쪽 트리와 오른쪽 트리 순서대로 입력이 들어온다.

출력해야 하는 것은 후위순회다. 이것은 왼쪽 -> 오른쪽 -> 루트 순서이다.

 

우선 입력을 받을 때 다른 문제와 달리 입력 갯수가 주어지지않았으므로 알아서 입력이 더이상 안될 때 끊어줘야한다.

try/ except 를 이용해 예외처리 되었을때 반복문을 종료해서 입력을 끝내야 할 것이다.

 

전위, 후위를 탐색하고 하위트리가 없을 경우 그것을 출력하는 방식으로 진행한다. 루트 보다 큰 값이 나올 경우 그 값을 기준으로 왼쪽트리, 오른쪽트리를 나눠 재귀로 이 과정을 반복해줄 것이다.

 

여기서 주의해야 할 것은 '재귀호출의 최대 깊이 설정'이다. prepost()를 그냥 진행할 경우 Recursion Error가 발생한다. 이를 방지하기 위해 sys.setrecursionlimit()를 설정한다. 재귀호출이 너무 깊어져 기본 재귀깊이제을 초과하지 않게 해준다.

가장 좋은 방법은 재귀말고 반복으로 풀 수 있으면 그렇게 하는 것이지만 이 문제는 재귀가 필요한 문제기 때문에 최대깊이 설정으로 해주었다.

 

*나의 코드

import sys
sys.setrecursionlimit(10 ** 6) #재귀호출 깊이제한 10^6
input = sys.stdin.readline

pre = []
while True:
    try:
        pre.append(int(input()))
    except:
        break


def prepost(start, end): # 전위순회 -> 후위순회
    if start > end: #종료 처리
        return
    mid = end + 1
    for i in range(start + 1, end + 1):
        if pre[i] > pre[start]:
            mid = i
            break
    prepost(start + 1, mid - 1)  # 왼쪽 트리
    prepost(mid, end)  # 오른쪽 트리
    print(pre[start])  # 루트 노드


prepost(0, len(pre) - 1)

 

 

*중요한 점

1. 재귀문제는 기본 재귀깊이를 초과할 수 있기 때문에 최대재귀 깊이를 설정해 주는 것이 좋다.
2. 이진트리에서 전위순회를 후위순회로 바꾸는 방법은 잘 숙지 해두도록 하자