[baekjoon] 백준 5639번(파이썬): 이진 검색 트리

문제

5639번: 이진 검색 트리

- 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

- 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다.

- 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다.

- 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

- 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 문제이다.

- 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다.

- 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

알고리즘

- dfs 탐색을 통해 문제를 수행한다.

- 입력 개수를 모름으로 while문과 try - except문을 통해 입력을 받는다.

- 서브 트리를 찾고 왼쪽과 오른쪽 서브 트리를 재귀적으로 탐색하여 노드 값을 출력한다.

코드

import sys
sys.setrecursionlimit(10 ** 9) # 재귀 허용 깊이를 수동으로 늘려주는 코드


# dfs 탐색
def dfs(start, end):

    # 시작과 끝 값이 역전시 리턴
    if start > end:
        return

    temp = end + 1

    # 서브 트리 찾기
    for i in range(start + 1, end + 1):
        # 루트 보다 크면 오른쪽 서브 트리
        if graph[start] < graph[i]:
            temp = i
            break

    dfs(start + 1, temp - 1) # 왼쪽 서브 트리 재귀적으로 탐색
    dfs(temp, end) # 오른쪽 서브 트리 재귀적으로 탐색

    print(graph[start])


# 입력이 없을때까지 반복하여 입력을 리스트에 추가한다.
graph = []
while True:

    try:
        graph.append(int(sys.stdin.readline()))

    except:
        break

dfs(0, len(graph) - 1)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법