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

문제링크

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

5639번: 이진 검색 트리

 

풀이

• 분류: 트리순회 + 이진탐색 느낌?
• 몰라서 풀이를 참고했다 ㅜㅜ 노드 클래스를 만들어서 풀려 하니까 insert, find 등의 함수를 다 구현해야하나 싶었다. 
• 참고 풀이를 설명하자면, 전위 순회로 받았기 때문에 처음 입력값인 50이 루트 노드 이다.
• 이진 트리이기 때문에 루트보다 큰 값은 오른쪽에 위치하게끔 인덱스를 설정해준다. 
• 그 인덱스를 기준으로 왼쪽 서브트리를 돌리고, 오른쪽 서브트리를 돌리는 것으로 푸는 것.

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

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

def postorder(start, end):
    if start > end:
        return
    mid = end + 1
    for i in range(start + 1, end + 1):
        if pre[start] < pre[i]: #루트보다 큰 값 찾아서
            mid = i #해당 인덱스를 기준
            break
    postorder(start + 1, mid - 1) #왼쪽 서브트리
    postorder(mid, end) #오른쪽 서브트리
    print(pre[start]) #노드 출력 

postorder(0, len(pre)-1)