[백준 5639] 이진 검색 트리

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

5639번: 이진 검색 트리

---

접근

이진 검색 트리는 루트 노드를 기준으로 루트 노드보다 작으면 왼쪽 서브트리로 크다면 오른쪽 서브트리에 저장한다. 이때 전위 순회의 결과가 주어진다고할 때 후위 순회의 결과를 출력해야 한다. 전위 순회이기 때문에 루트 노드를 먼저 방문하게 된다. 따라서 맨 처음 나오게 되는 숫자가 루트 노드에 저장된 수이다.

 

이제 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누면 될 것이다. 이를 재귀함수로 구현하며 현재 방문한 루트 노드를 재귀함수가 종료되고 되돌아온 후에 출력하면 후위 순회의 결과가 출력될 것이다.

 

구현

• post_order라는 함수는 현재 범위 내에서 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누는 함수이다.
• 이후 두 개의 재귀호출이 종료된 후에 현재 루트 노드를 출력하므로서 후위 순회의 결과가 나오게 된다.
• 먼저 start는 해당 범위의 첫 번째를 가리키기 때문에 루트 노드가 된다.
• 이제 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 찾게 되는데 
• 현재 범위를 탐색하다가 루트 노드보다 큰 수가 나왔을 때 pivot에 인덱스를 저장한다.
• 이제 pivot을 통해 왼쪽과 오른쪽으로 나누어 재귀 호출을 진행한다.
• 재귀 호출에서 모두 돌아온 후에 root를 출력하면서 루트 노드를 가장 마지막에 방문하는 것을 구현한다.

def post_order(start, end):
    if start > end:
        return

    root = pre_order[start]
    pivot = end + 1
    for i in range(start+1, end+1):
        if root < pre_order[i]:
            pivot = i
            break
    post_order(start+1, pivot - 1)
    post_order(pivot, end)
    print(root)

---

전체 코드

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

def post_order(start, end):
    if start > end:
        return

    root = pre_order[start]
    pivot = end + 1
    for i in range(start+1, end+1):
        if root < pre_order[i]:
            pivot = i
            break
    post_order(start+1, pivot - 1)
    post_order(pivot, end)
    print(root)

pre_order = []
while True:
    try:
        pre_order.append(int(input()))
    except:
        break
if pre_order:
    post_order(0, len(pre_order) - 1)