[백준] 9934번 완전 이진 트리 파이썬 코드

코드

n = int(input())
path = [0,*map(int, input().split())] # 숫자를 맞춰주기 위해
tree = []

while path:
  if len(path) == 1: break
  level = [] # tree level을 모아줄 리스트
  road = [] # 남는 수를 모아줄 리스트
  for i in range(0, len(path)):
    if i%2 == 1: level.append(path[i]) # 홀수 번째 있는 것들이 리프 노드
    else: road.append(path[i]) # 나머지는 남기기
  tree.append(level) # 트리에 넣어준다
  path = road # 반복
  
tree.sort(key=lambda x: len(x)) # 개수를 기준으로 정렬

for i in tree:
  print(*i)

dfs의 역순을 구해볼까 하다가 규칙을 찾아서 해결한 문제. 완전이진트리가 아니라면 이 방법은 사용할 수 없을 것 같다. 재귀로 푼 풀이도 학습을 해야할 듯.

 

완전이진트리: 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다.