[백준5639&파이썬] BST의 preorder를 postorder로 변환하는 방법

# 문제

백준 5639 이진 검색 트리 파이썬 풀이

5639번: 이진 검색 트리

# 코드

import sys
sys.setrecursionlimit(10**6)
def printSolve(arr) :
  for i in arr :
    print(i)

# 몇개인지 모르는걸 입력받을때는 아래와 같이 수행하자.
bst = list()
while True :
  try :
    bst.append(int(sys.stdin.readline().strip()))
  except :
    break

l = 0
r = len(bst)-1
result = list()
def sub(l,r) :
  global result,bst

  if l == r :
    result.append(bst[r])
    return

  if l > r :
    return

  root = bst[l]
  mid = l
  for i in range(l+1,r+1) :
    if root < bst[i] :
      mid = i
      break

  # print(f"root : {root} , l: {l},mid : {mid} r : {r} , result : {result}")
  if mid == l : # 큰거를 찾지 못했을때
    sub(l+1,r)
  else :
    # 여기서 mid가 발견되지 않을 경우 처리해야 할듯?
    sub(l+1,mid-1)
    sub(mid,r)
  result.append(root)

sub(l,r)
printSolve(result)

## 최적화 풀이

l = 0
r = len(bst)-1
result = list()
def sub(l,r) :
  global result,bst

  if l > r :
    return

  root = bst[l]
  mid = r + 1
  for i in range(l+1,r+1) :
    if root < bst[i] :
      mid = i
      break

  # print(f"root : {root} , l: {l},mid : {mid} r : {r} , result : {result}")
  sub(l+1,mid-1)
  sub(mid,r)
  result.append(root)

sub(l,r)
printSolve(result)

 

# 풀이

• preorder의 특징을 잘 파악해보면, root -> L -> R 순으로 이동하기 때문에 root를 기점으로 L과 R로 분리될 수 있는 특징이 있었다.
• L과R의 각각 sub-bst로 나뉨을 알 수 있었다. 이 과정에서 그 나누어 지는 포인트를 찾는 방법은 현재 root노드의 값보다 큰 값이 나오는 인덱스지점이 R sub트리가 나누어지는 지점이다.
• sub tree를 찾아 나가면서 leaf가 없는 sub트리가 발견되면 끝나는 지점이다.

  sub(l+1,mid-1)
  sub(mid,r)
  result.append(root)

• 위와 같이 마지막 지점에 append를 한번 시켜준다.
• 코드를 최적화 시키지 못했다. 루트보다 큰 값이 존재하지 않는 즉 sub트리가 왼쪽(L)은 없고 오른쪽(R)만 존재할 경우의 과정을 최적하는 방법이 마땅히 떠오르지 않았다.
• mid를 L+1로 초기값을 설정함으로써, 위의 조건(루트보다 큰 값이 존재하지 않을 경우)일 때 한번만 sub트리를 두개로 분리하지 않고 한번만 분리하도록 간단히 처리 할 수 있었다.
•