BOJ 5639 이진 검색 트리

문제

접근 방법

이진 검색 트리는 왼쪽은 모두 루트보다 더 작고, 오른쪽은 모두 루트 노드보다 큰 성질을 가지고 있다. 이 성질을 이용해 후위 순회 결과로 이진 검색 트리의 구조를 파악할 수 있다.

처음 노드는 무조건 루트 노드이므로 고정시키고, 이 노드보다 작은 애들은 모두 왼쪽 subtree에 존재하는 노드들이다. 루트 노드보다 커지는 노드들부터는 오른쪽 subtree이다. 이 과정을 코드로 표현하면 다음과 같다.

정답 코드

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

nums = []
while True:
  try:
    num = int(input())
    nums.append(num)
  except ValueError:
    break

def traversal(arr):
  if len(arr) == 0:
    return
  root = arr[0]
  left_arr = []
  right_arr = []
  only_left = True
  for i in range(1, len(arr)):
    #오른쪽 subtree가 나타나면
    if root < arr[i]:
      left_arr = arr[1:i]
      right_arr = arr[i:]
      only_left = False
      break

  if only_left:
    left_arr = arr[1:]
  traversal(left_arr)
  traversal(right_arr)
  print(root)

traversal(nums)