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

본문 링크

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

def DFS(start,end):

    if start>end:
        return

    index=end+1 #오른쪽 노드가 없을 수도 있기 때문에 끝값을 지정함.
    for i in range(start+1,end+1):
        if Tree[start]<Tree[i]: #왼쪽 서브 트리 범위를 구한다.
            index=i
            break

    DFS(start+1,index-1) #왼쪽 서브트리
    DFS(index,end) # 오른쪽 트리
    print(Tree[start])


Tree=[]

while True:
    try:
        Tree.append(int(input()))
    except:
        break
DFS(0,len(Tree)-1)

📌 어떻게 접근할 것인가?

트리의 전위순회 결과를 후위순회한 결과를 출력하는 문제이다.

$Tree$ 리스트를 입력받고 DFS 를 사용한다.

먼저 트리의 왼쪽노드를 우선탐색 해준다.
후위순회는 왼쪽-오른쪽-루트 순으로 탐색하기 때문에
전위순회에서 가장 작은값이 가장 왼쪽에 있으므로 가장 작은값을 찾은뒤에
이후 오른쪽 정점을 탐색한다.

index 가 왼쪽서브트리의 범위라고 할때

• $DFS(start+1,index-1)$ #왼쪽 서브트리
  $DFS(index,end)$ # 오른쪽 트리
  

와 같은 순서대로 탐색하게 된다.

✅ 코드에서 주의해야할점

• 입력횟수는 주어지지않기때문에 $try$-$except$ 문법을 사용한다.
• 왼쪽서브트리의 범위를 잡아주는 index 값은 오른쪽노드가 없을수 있기때문에(가장큰값) end+1 로 잡아준다.