[백준 9934] 완전 이진 트리 (python)

9934번: 완전 이진 트리

---

BFS를 통해 해결하자!

 

1. 배열의 중간값이 루트이고 루트를 기준으로 왼쪽 서브루트와 오른쪽 서브루트로 나눌 수 있다.
2. makeTree함수를 통해 서브트리와 현재 깊이를 전달한다.

 

import sys
input = sys.stdin.readline

K = int(input())
_input = list(map(int, input().split()))
tree = [[] for _ in range(K)]


def makeTree(arr, x):
    mid = (len(arr)//2)
    tree[x].append(arr[mid])
    if len(arr) == 1:
        return
    makeTree(arr[:mid], x+1)
    makeTree(arr[mid+1:], x+1)


makeTree(_input, 0)
for i in range(K):
    print(*tree[i])