백준 | 5639 : 이진 검색 트리(Python/파이썬)

문제

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

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

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

 

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

 

 

입력

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

 

 

출력

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

 

---

 

풀이

 

풀이과정

1. 루트를 기준으로 왼쪽노드와 오른쪽노드를 분류하는 것을 반복

2. 루트만 존재하고 양쪽 노드가 없을때까지 분류하여 루트를 순차적으로 출력

 

코드

import sys
sys.setrecursionlimit(10**9)

preorder_arr = []

# 엔터 들어올 때까지 입력
while True:
    try:
        a = int(input())
        preorder_arr.append(a)
    except:
        break


def postorder(root_idx, end_idx):
    if root_idx > end_idx:
        return
    
    global preorder_arr
    
    # 만약 root보다 큰 값 없는 경우 전부 왼쪽 서브트리로 취급
    right_start = end_idx + 1

    for i in range(root_idx + 1, end_idx + 1):
        if preorder_arr[root_idx] < preorder_arr[i]:
            right_start = i
            break
    
    # root 다음부터 왼쪽 서브트리 탐색
    postorder(root_idx + 1, right_start - 1)

    # 왼쪽 서브트리 탐색 끝나면 오른쪽 서브트리 탐색
    postorder(right_start, end_idx)

    # 왼쪽, 오른쪽 서브트리 탐색 끝나면 root 출력
    print(preorder_arr[root_idx])


postorder(0, len(preorder_arr) - 1)