백준 5639번: 이진 검색 트리 (Python)

접근

트리 순회 문제 중, 인오더와 포스트오더가 주어졌을 때 프리오더를 구하는 문제가 있었는데 그 문제와 유사하게 생각하면 좋다. 이번에는 프리오더만 주어지지만 추가적으로 '이진 검색 트리'라는 트리의 속성을 이용하여 문제를 해결할 수 있다.

유사 문제: 2021.04.29 - [코딩/백준 (Python)] - 백준 2263번: 트리의 순회 (Python)

백준 2263번: 트리의 순회 (Python)

주어진 이진 검색 트리의 프리오더를 보면 다음과 같이 생각할 수 있다.

1. 주어진 프리오더의 루트는 첫번째 요소이다.
2. 이후 주어진 프리오더를 탐색하다가 루트보다 커지는 첫번째 요소부터 루트의 오른쪽 트리이다.
3. 오른쪽 트리의 시작을 기준으로 나누면 한개의 프리오더는 루트 / 왼쪽트리 프리오더 / 오른쪽트리 프리오더 로 나눌 수 있다.

그림으로 보면 다음과 같다.

코드

import sys

sys.setrecursionlimit(10 ** 9)
preorder = []
while True:
    try:
        preorder.append(int(sys.stdin.readline()))
    except:
        break
postorder = []


def postorderset(preorder, left, right):
    if left > right:
        return
    root = preorder[left]
    ls = left + 1
    re = right
    rs = right + 1
    for i in range(right - left + 1):
        if i == 0:
            continue
        if preorder[left + i] > root:
            rs = i + left  # 루트보다 첫번째로 커지는 수를 오른쪽 프리오더의 시작으로 정해준다
            break
    le = rs - 1
    postorderset(preorder, ls, le)  # 왼쪽 프리오더 순환
    postorderset(preorder, rs, re)  # 오른쪽 프리오더 순환
    postorder.append(root)  # root를 preorder 리스트에 추가


postorderset(preorder, 0, len(preorder) - 1)
for i in postorder:
    print(i)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!