백준 9934 완전 이진 트리 / C++

문제 : 9934

풀이 point

중위순회와 완전이진트리의 특성을 활용
트리를 재구성 한다고 생각하면 편하다.
중위 순회 + 완전이진트리의 특성 상 가운데값이 루트에 해당함
중위 순회로 입력받은 값을 반으로 나누었을 때 가운데가 루트, 또 반으로 나누면 그 가운데가 부분트리의 루트 값이 된다.

그 값들을 루트 깊이에 알맞게 저장하면 끝

풀이 방법

이진검색처럼 가운데 값을 찾고 반을 뚝 자른다. 갈라진 반에서 또 가운데 값을 찾고 반으로 자르는 것을 구현

트리의 레벨에 맞게 각 노드를 넣어주어야한다. level이라는 이차원 벡터를 통해 depth에 맞는 노드를 push해준다.

이때 level.resize(k)를 하지 않으면 에러가 발생한다. level[depth]를 할 때 level[ [ ] ]의 크기가 0이기 때문에 depth가 인덱스 에러를 일으킨다.

undefined

코드

//백준 9934, 완전 이진 트리  

#include <iostream>
#include <vector>

std::vector<std::vector<int>> level;

int k;
int tree[1050];
void recur(int start, int end, int depth){
    if(start > end) return;
    int mid = (start + end) / 2;
    
    level[depth].push_back(tree[mid]);
    
    recur(start, mid-1, depth+1);
    recur(mid+1, end, depth+1);
    
}

int main(){
    std::cin >> k;
    int size = (1<<k)-1;
    for(int i{0}; i<size; ++i){
        std::cin >> tree[i];
    }
    level.resize(k); //resize 해야함
    
    recur(0, size-1, 0);
    
    for(int i{0}; i<k; ++i){
        for(auto l : level[i]){
            std::cout << l << ' ';
        }
        std::cout << '\n';
    }
    
    
    
    return 0;
}

사족

처음에는 완전이진트리를 통해 자식의 자식을 계속 구하는 문제인가 싶었다. 근데 입력으로 들어오는 것이 중위순회 값이고, 가운데 값들이 루트임을 알아야하는 문제였다. 잘못된 이해 때문에 굉장한 헛고생을 했다... tree[2*idx + 1]등 이상한 짓은 다했다.