[백준] 5639 - 이진 검색 트리

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

5639번: 이진 검색 트리

문제 한줄 이해

- 전휘 순회로 출력된 결과를 가지고 후위 순회한 결과 뽑기

 

생각난 풀이

1번째 방법: 먼저 전회 순회를 통해 루트를 기준으로 루트보다 큰 값을 만나는 순간 왼쪽 오른쪽으로 나눠진다는 것은 알아냈지만 이를 어떻게 활용해야할까 고민을하다가 계속 파고드네????? 재귀를 써야하나??? 접근해봤다.

예제를 보면 50 30 24 5 28 45 98 52 60 이렇게 전회 순회된 결과에서 아래와 같이 규칙성을 찾을 수 있다.

여기서 보면 root를 기준으로 root보다 큰값을 만나는 순간 왼쪽 자식과 오른쪽 자식으로 나누어진다는 것을 알 수 있다.

그렇다면 배열의 인덱스값을 매개 변수로 적절히 넘겨 줘야 한다.

import sys
sys.setrecursionlimit(10**6)
node = []

while True:
    try:
        node.append(int(sys.stdin.readline()))
    except:
        break
        
def post(start, end):
    if start > end-1:
        return
    #탐색 전 mid는 노드 갯수로
    mid = end 
    for i in range(start+1 , end):
        if node[start] < node[i]:
            mid = i
            break
    #왼쪽 자식
    post(start+1,mid)
    #오른쪽 자식
    post(mid,end)
    #후의 순회는 부모가 마지막에 출력
    print(node[start])
    
#배열의 처음과 끝을 담아주는건 당연!
post(0,len(node))