[백준] 5639번-(Python 파이썬) - Tree

1648 단어 백준treetree

문제링크 : https://www.acmicpc.net/problem/5639

이번 문제는 순회 문제인데 처음엔 전혀 감이 오질 않아 다른분의 코드를 보고 공부하였다.
밑에 코드는 참조한 글여기서 설명과 코드를 보면서 공부한 코드이다.

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

def postorder(start, end):
  if start > end:         
    return
  
  root = preorder[start]     
  idx = start + 1

  while idx <= end:       
    if preorder[idx] > root: 
      break
    idx += 1
  
  postorder(start + 1, idx - 1)    
  postorder(idx, end)       
  print(root)

preorder = []
while 1:
  try:
    preorder.append(int(input()))
  except:
    break

postorder(0, len(preorder)-1)

제출 후 더 빠르게 수정한 코드

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

preorder = []

def postorder(start, end):
    if start >= end:
        return

    root = preorder[start]

    if preorder[end - 1] <= root:
        postorder(start + 1, end)
        print(root)
        return

    for i in range(start + 1, end):
        if preorder[i] > root:
            idx = i
            break

    postorder(start + 1, idx)
    postorder(idx, end)
    print(root)

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

postorder(0, len(preorder))

좋은 웹페이지 즐겨찾기