[백준,c++] 9934번 - 완전 이진 트리

문제

9934번: 완전 이진 트리

 

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int>height[1025];
vector<int>v(1025);
void inorder(int start, int end, int level){
    if(start > end) return;
    int mid = (start+end)/2;
    height[level].push_back(v[mid]);
    
    inorder(start, mid-1, level+1);
    inorder(mid+1, end, level+1);

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int K; cin>>K;
    
    for(int i=0; i<pow(2,K)-1; i++){
        cin>>v[i];
    }
    
    inorder(0, pow(2,K)-2, 1);
    
    for(int i=1; i<=K; i++){
        for(auto it: height[i]){
            cout<<it<<' ';
        }
        cout<<'\n';
    }
}

 

풀이

이진트리를 중위 순회(inorder) 방식으로 순회하면서 각 레벨 별 노드를 전부 출력하는 문제입니다.

중위 순회의 개념은 아래 게시글에서 정리한 적이 있습니다.

이진트리 탐색 운행법

해당 문제를 해결하는 아이디어는 루트 노드(mid)를 찾은 다음 루트 노드를 기점으로 다시 좌우로 루트 노트(mid)를 찾는 방식으로 풀 수 있습니다.

1. 루트 노드 같은 경우는 중간값이 루트값이 된다.
2. 루트를 구한 후에는  [처음~중간-1], [중간+1~끝]으로 범위를 나누고 각각의 범위에서 다시 중간값을 찾는다.