BOJ [이진검색트리]

문제

2022-03-31

문제 보기

트리를 전위 탐색한 결과가 input으로 주어진다.

왼쪽 트리는 루트보다작고 오른쪽 트리는 루트보다 큰 이진트리이다.

풀이

아이디어

카카오 트리문제처럼 class를 써서 root보다 작은애들은 left로 넘기고 root보다 큰애들은

right로 넘겨서 풀었는데 메모리 초과가 났다.

class는 메모리를 많이 잡아먹는 모듈이므로 안쓸 수 있으면 안쓰고 풀자.

풀이

재귀를 써야되긴 하는데 class를 선언하지 말고 pre 에서 바로 post로 바꾸는 방식을 쓰자.

즉, tree를 구할 필요가 없이 그냥 바로 바꾸는 것 preorder은 처음이 root이므로

그 다음 원소중 root 보다 커지면 거기부터는 right로 넘긴다.

left넘기고, right넘기고 root 출력하면 된다. 재귀로.

answer로 return 해야 되는 문제면 answer list를 선언 후 함수의 마지막에 root를

append 해주면 된다.

코드

import sys
sys.setrecursionlimit(10 ** 7)

def preToPost(pre):

  root = pre[0]
  
  right_start = 1
  
  for i in range(1,len(pre)):
    if pre[i] > root:
      right_start = i
      break
  if right_start >1:
    preToPost(pre[1:right_start])
  if len(pre)>right_start:
    preToPost(pre[right_start:])
  print(root)

preorder = []

while True:
  try:
    preorder.append(int(input()))
  except:
    break

preToPost(preorder)