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

문제

 

 

 

풀이

트리를 순회하며 각 노드의 번호를 구하는 문제이다.

트리는 중위순회를 진행하라고 설명에서 작성되어 있다.

(중위순회란? LEFT - ROOT - RIGHT 순서대로 순회하는것.)

 

재귀를 통하여 문제를 풀고자 하였다.

한 노드의 왼쪽 자식노드 인덱스는 2^n+1 이고 오른쪽은 2^n+2 이기 때문이다.

따라서 아래와 같이 재귀함수를 구성하였다.

def back(n):
    if n>=max_count:
        return
    back(2*n + 1)
    ans[n] = lst.popleft()
    back(2*n + 2)

 

루트 노드들은 먼저 입력받은 숫자에서 가장 왼쪽 값을 빼서 넣어주며 정답 리스트인 ans를 완성하였다.

 

이후에  for문을 통해 각 레벨마다 값을 출력해주며 마무리하였다.

 

코드

from collections import deque
n=int(input())
max_count= 2**n-1
lst = list(map(int,input().split()))
lst = deque(lst)
ans = [-1 for i in range(max_count)]

def back(n):
    if n>=max_count:
        return
    back(2*n + 1)
    ans[n] = lst.popleft()
    back(2*n + 2)
back(0)

for i in range(n):
    for j in range(2**i-1,2**(i+1)-1):
        print(ans[j], end=' ')
    print()