백준 9934 : 완전 이진 트리

https://www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

 

해결 방법 : 트리, 재귀

• 입력으로 주어지는 방문 순서는 트리의 Inorder 순회 결과와 같다.
  • 주어지는 트리가 완전 이진 트리이기 때문에 방문 순서의 정 가운데가 root가 된다.
  • 양쪽으로 나누어진 방문 순서 리스트 또한 하나의 완전 이진 트리이며 위와 같이 생각 할 수 있다.
• 따라서 "재귀 호출의 깊이 = 트리의 level"과 같다.

import sys
input = sys.stdin.readline

def solution(K, order):
    treeLevels = {i : [] for i in range(1, K+1)} # 트리 레벨 : 노드 번호 

    def devide(level, left, right): # 리스트를 양분하는 재귀 함수
        if left > right: return
        mid = (left + right) // 2 # 가운데 값 = 현재 트리의 root

        treeLevels[level].append(order[mid])

        devide(level + 1, left, mid - 1)
        devide(level + 1, mid + 1, right)

    devide(1, 0, len(order) - 1)

    answer = ''
    for n in treeLevels.values():
        temp = ' '.join(n)
        answer += temp + '\n'

    return answer

if __name__ == '__main__':
    K = int(input())
    order = list(input().strip().split())
    result = solution(K, order)
    print(result)