백준 9934번 완전 이진 트리: C언어 풀이

백준 9934 완전 이진 트리 문제의 C언어 해설입니다.
트리를 직접 구현하는 방법 대신, 중위 순회 결과가 저장된 배열에서 층별 순회 결과를 수학적으로 도출하여 해결하는 방법을 설명합니다.

전략

트리 만들지 않기

트리를 구성해서 bfs를 하면 간단한 문제이다.
근데 그냥 빌딩 번호가 저장된 배열을 층별 순회 순서대로 출력하면 더 간단하지 않을까?

중위 순회 순서대로 저장된 배열을 층별로 읽을 수 있는 어떤 적절한 규칙이 분명 있을 것이다 라고 생각했다.
그렇게 노트랑 팬 들고 삽질하면서 다음 규칙을 찾았다.

level 3의 첫 번째 노드 왼쪽에는 깊이가 2인 포화 이진 트리가 존재한다.
level 3의 각 노드 사이에는 깊이가 3인 포화 이진 트리가 존재한다.

중위 순회 결과는 왼쪽부터 순서대로 배열에 저장되어 있다.
level 3 첫 번째 노드의 인덱스는 깊이 2인 포화 이진 트리 속 노드의 수가 될 것이다.
level 3 두 번째 노드의 인덱스는 첫 번째 인덱스에서, 깊이 3인 포화 이진 트리 속 노드의 수 + 1 이 될 것이다.

이를 일반화 해보자.
깊이 $d$ 인 포화 이진 트리에서 레벨 $l$ 인 각 노드의 아래에는 깊이가 $d-l$ 인 포화 이진 트리가 쌓여있다.

따라서 레벨 $l$인 각 노드의 인덱스는
$a_{n}= 2^{d-l} -1 + 2^{d-l+1}n$이 된다.

코드

#include <stdio.h>

#define MAX_ARRAY_SIZE 1024 + 1

int tree_size(int depth);

int main(void)
{
    int depth;
    scanf("%d", &depth);

    // Get Input: Inorder 
    int tree[MAX_ARRAY_SIZE];
    int num_nodes = tree_size(depth);
    for (int i = 0; i < num_nodes; i++)
    {
        scanf("%d", &tree[i]);
    }

    // Output: Level Order
    for (int curr_depth = 1; curr_depth <= depth; curr_depth++)
    {
        int subtree_depth = depth - curr_depth;

        int start = tree_size(subtree_depth);
        int inc = tree_size(subtree_depth + 1) + 1;
        for (int i = start; i < num_nodes; i += inc)
        {
            printf("%d ", tree[i]);
        }
        printf("\n");
    }
}

int tree_size(int depth)
{
    return (1 << depth) - 1;
}