백준 9934번. 완전 이진 트리(c++) / Tree

중위순위의 특징?을 통해서 풀 수 있는 문제이다.

중위순회의 특징은 Start~End의 범위를 가지고 있는 배열에서 Mid = (Start+End)/2;의 값이 루트가 된다는 것이다.

그렇게 계속 재귀를 돌면, level별로 노드를 구할 수 있다.

 

// 완전이진트리
#include <iostream>
#include <vector>
 
using namespace std;
 
int k, node;
vector<int> height[11];
int arr[1100] = {0, };
 
void dfs(int Start, int End, int level)
{
    int mid = (Start+End)/2;
    height[level].push_back(arr[mid]);
 
    if(Start==End){
        return;
    }
 
    dfs(Start, mid-1, level+1);
    dfs(mid+1, End, level+1);
}
 
int main()
{
    cin>>k;
    int cnt = 1;
    for(int i=0; i<k; i++){
        cnt *= 2;
    }
    cnt -= 1;
    for(int i=0; i<cnt; i++){
        cin>>node;
        arr[i] = node;
    }
 
    dfs(0, cnt-1, 1);
 
    for(int i=1; i<=k; i++){
        for(int j=0; j<height[i].size(); j++){
            cout<<height[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}