[백준][C++] 9934 완전 이진 트리

www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

 

 

 

알고리즘 종류

    - 트리

    - 그래프

 

 

 

사고 과정

    - 중위 순회는 root를 중간에 출력하게 된다. 그리고 문제에서 제시된 트리는 완전 이진 트리이다. 따라서 중위 순회의 가운데 있는 값은 root가 된다.

        1. 순회 배열에서 mid로 root를 찾는다.

        2. root를 기준으로 좌우 트리를 나누고 다시 mid로 root를 찾는다.

 

 

 

구현(C++)

#include <vector>
#include <iostream>
#include <math.h>
 
using namespace std;
 
 
int k;
vector<int> bag;
vector<int> answer[11];
 
void search(int s, int e, int depth){
    
    if(s == e) {
        answer[depth].push_back(bag[s]);
        return;
    }
    
    // 완전 이진 트리이고 중위 순회이므로, 가운데 있는 값은 root가 된다.
    int mid = (e+s)/2;
    answer[depth].push_back(bag[mid]);
    
    // root를 제외하고 좌우로 나누어서 탐색을 진행한다.
    search(s, mid-1, depth+1);
    search(mid+1, e, depth+1);
}
 
 
int main(){
    cin >> k;
    
    for(int i=0; i<pow(2,k)-1; i++){
        int num;
        cin >> num;
        bag.push_back(num);
    }
 
    search(0, bag.size()-1, 0);
    
    for(int i=0; i<k; i++){
        for(int j=0; j<answer[i].size(); j++){
            cout << answer[i][j] << " ";
        }
        cout << endl;
    }
}

 

 

 

시행착오