백준 9934 완전 이진 트리

https://www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

주어진 입력으로 중위 순회가 되도록 만드는 문제입니다.

 

중위 순회 : 트리를 왼쪽 자식 -> 부모 -> 오른 자식 순으로 탐색

 

모든 depth에 자식을 2개씩 갖는 포화 이진 트리이므로 (문제 제목은 완전 이진 트리이지만 문제에 2^k-1 개 노드 갖는다고 함) 인터벌의 가운데가 부모가 되며 depth를 1씩 올리며 재귀를 돌면 됩니다.

 

코드는 다음과 같습니다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int k;
vector<int> nums;
vector<int> tree[10];
bool check[1025];
int total;

void init()
{
    cin >> k;
    int num;
    
    total = (int)pow(2, k) - 1;
    for(int i = 0; i < total; i++) {
        cin >> num;
        nums.push_back(num);
    }
    memset(check, false, sizeof(check));
}

void travel(int depth, int start, int last)
{
    
    // 중위 순회 되도록 만들기 (왼 부모 오 순 되도록 만듬)
    int mid = (start + last) / 2;
    int num = nums[mid];
    if(check[num])
        return;
    
    tree[depth].push_back(num);
    check[num] = true;
    
    travel(depth + 1, start, mid);
    travel(depth + 1, mid + 1, last);
}


int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    
    travel(0, 0, total);
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < tree[i].size(); j++) {
            cout << tree[i][j] << ' ';
        }
        cout << '\n';
    }
}