[BOJ] 5639번 : 이진 검색 트리(재귀, dfs)

접근

이진 탐색 트리의 전위 순회 결과만을 이용해서, 후위 순회 결과를 복원해내는 문제이다. 이진 탐색 트리의 전위, 중위 순회결과를 이용해서 트리를 복원해내는 방법이 있는데, 그 방법을 차용해서 해결했다.

 

해결

전위, 중위 순회 결과만이 있다면, 이진 탐색 트리는 복원이 가능하다.

• 전위 순회 결과는 항상 맨 처음의 값이 루트 노드이다.
• 중위 순회 결과는 `Left - Root - Right` 순서이기에, 특정 노드 기준으로 왼쪽 부분결과는 Root보다 작은 값들이고, 오른쪽 부분 결과는 큰 값들이다.

이 두가지 성질을 이용한다면, 이진 탐색 트리를 복원해낼 수 있다. 하지만 우리는 중위 순회 결과가 없기에, 중위 순회 결과를 만들어내야한다. 그냥 그건 간단하다. Root Node보다 작은 값들을 찾아서, Left로 인식하고, 큰 값들을 찾아서, Right으로 인식하면 된다.

 

또 우리는 어차피 후위 순회 결과만이 필요한거기에 이진 탐색 트리를 직접 다 만들 필요는 없다. 그냥 재귀를 사용해서, 후위 순회 결과(Left - Right - Root)를 출력하도록 구성해주자.

 

※ Python 사용자면, 시스템 recursionlimit을 더 늘려주자.. 기본 recursionlimit은 3,000으로 너무 작다. 안 그럼 recursionerror가 발생해서 맞는 코드인데도 틀린다..

코드

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

bin_tree_pre = []

while True:
    try:
        input_num = int(input())
        bin_tree_pre.append(input_num)
    except:
        break
        
def dfs(root_node, order_res):
    l_node = []
    r_node = []
    for i in range(1, len(order_res)):
        if order_res[i] < root_node:
            l_node.append(order_res[i])
        else:
            r_node.append(order_res[i])
    if l_node:
        dfs(l_node[0], l_node)
    if r_node:
        dfs(r_node[0], r_node)
    print(root_node)
    
dfs(bin_tree_pre[0], bin_tree_pre)