[백준][Python] 9934번 완전 이진 트리

9934번: 완전 이진 트리

 

코드

import sys

k = int(input())
num = list(map(int,sys.stdin.readline().split()))
length = len(num)
tree = [[] for _ in range(k)]
def get_num(first,last,k):
    if first == last:
        tree[k].append(num[first])
        return
    mid = (first+last) // 2
    tree[k].append(num[mid])
    get_num(first,mid-1,k+1)
    get_num(mid+1,last,k+1) 

get_num(0,length-1,0)
for i in range(k):
    for j in tree[i]:
        print(j,end=' ')
    print()

 

설명

중위 순회(inorder)를 반대로 실행해야 된다.

출력값을 보면 입력받은 리스트의 가장 가운데 값이 트리의 루트가 된다. 재귀를 사용해서 first와 last를 계속 바꿔주면서 가운데 값을 찾아냈다. 

---

리스트에 있는 값을 한 줄에 출력하고 싶으면 print(*list)를 쓰면 된다는 사실을 알게 됐다.

list = [1,2,3,4]
print(*list)   # 1 2 3 4 와 같이 출력됨