[백준 5639] 이진 검색 트리 - 파이썬(Python) - 골드5(그래프 탐색, 트리, 재귀)

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

5639번: 이진 검색 트리

문제

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

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

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

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

입력

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

출력

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

 

 

---

이진 검색 트리(Binary Search Tree)의 전위 순회의 결과가 주어졌을 때, 후위 순회의 결과를 구하는 문제이다.

 

전위 순회는 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 방법이다.

따라서, 전위 순회 결과값의 첫 번째 값은 무조건 트리의 루트 노트라고 할 수 있다. 루트 노드보다 값이 큰 값이 있다면, 그 이후부터는 오른쪽 서브 트리이기 때문에 값이 커지는 순간을 mid로 두고, 이후 양 서브 트리들을 다시 재귀하며 탐색한다.

 

루트 노드 / 왼쪽 서브 트리 / 오른쪽 서브 트리

50

30

24

5

28

45

98

52

60

 

함수 내에서 mid를 right+1로 초기화하는 것은 모든 원소들이 루트 노드보다 작은 경우 다음 차례에 바로 return되도록 하기 위해서이다.

 

 

<< 최종 코드 >>

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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


def post_order(left, right):
    if left > right:
        return
    mid = right + 1
    for i in range(left+1, right+1):
        if nums[left] < nums[i]:
            mid = i
            break

    post_order(left+1, mid-1)
    post_order(mid, right)
    print(nums[left])


post_order(0, len(nums)-1)