[골드 4] 백준 5639 - 이진 검색 트리 (파이썬)

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

풀이

전위 순회를 후위 순회로 변환하는 구현을 진행해야한다.

즉, 전위 순회 결과가 주어졌을 때, 해당 트리의 후위 순위 결과를 출력해야한다.

입력은 전위 순회 결과이며, 이진 검색 트리 조건이 적용된다.

• 왼쪽 자식 < 부모 < 오른쪽 자식

def postorder(start, end):
    if start >= end:
        return
    
    root = preorder[start]  # 현재 서브트리의 루트

    # 오른쪽 서브트리의 시작 인덱스를 찾기
    right = start + 1
    while right < end and preorder[right] < root:
        right += 1

    # 왼쪽 서브트리 순회
    postorder(start + 1, right)

    # 오른쪽 서브트리 순회
    postorder(right, end)

    # 루트 출력 (후위 순회이므로 마지막에 출력)
    print(root)

preorder[start]는 항상 서브트리의 루트 노드이며, 그 다음부터 preorder[right] < root 이면 왼쪽 서브트리에 속한다.

조건이 깨지는 최초의 right는 오른쪽 서브트리의 시작점이며, 그 구간들을 기준으로 재귀적으로 분할하여 탐색한다.

코드

# 백준 5639 - 이진 검색 트리
# 분류 : 트리

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

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

def postorder(start, end) :
    if start >= end :
        return
    root = preorder[start]

    right = start + 1
    while right < end and preorder[right] < root :
        right += 1
    
    postorder(start + 1, right)
    postorder(right, end)

    print(root)

postorder(0, len(preorder))