백준 9934번: 완전 이진 트리

문제

문제 바로가기> 백준 9934번: 완전 이진 트리

풀이

완전 이진 트리이므로 트리의 크기는 2^k-1이다. 먼저 cnt를 이용하여 트리의 크기를 예측한 후, 그 만큼의 입력을 받았다. 그리고, 재귀를 사용하여 dfs 탐색을하며 각 level별로 node를 차례로 저장 후 출력해주었다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> height[11];
int tree[1025] = {0, };

void dfs(int begin, int end, int level){
    int mid = (begin+end)/2;
    height[level].push_back(tree[mid]);

    if(begin == end) return;
    
    dfs(begin, mid-1, level+1);
    dfs(mid+1, end, level+1); 

}

int main(){
    int k, cnt=1, node; cin>>k;
    for(int i=0; i<k; i++) cnt*=2;
    for(int i=0; i<cnt-1; i++){
        cin>>node; tree[i]=node;
    }

    dfs(0, cnt-2, 1);

    for(int i=1; i<k+1; i++){
        for(int j=0; j<height[i].size(); j++){
            cout << height[i][j] << ' ';
        } cout << '\n';
    }
}