백준 9934 완전 이진 트리 (C++)

9934번: 완전 이진 트리

재귀를 이용한 문제이다. 문제를 보면 상근이는 빌딩을 중위 순회 방식으로 빌딩에 들어가고 있다. 그렇기에 주어진 진입 순서의 중앙이 트리의 루트가 되고, 줃앙을 기준으로 왼쪽, 오른쪽으로 나누어 다시 각각의 중앙이 루트가 되고 이를 반복하게 된다. 이를 재귀로 구현해주고 트리를 구해 출력해주었다.
쉽게 풀 수 있었던 문제였다. 오랜만에 순회 관련 문제를 풀어보면서 전위 중위 후위에 대해 다시 알아볼 수 있었던 좋은 문제였다.

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

using namespace std;

int K;
int A[1024];
vector<int> v[10];

void findTree(int start, int end, int level) {
    if (start == end) {
        v[K - level].push_back(A[start]);
        return;
    }

    int mid = (start + end) / 2;
    v[K - level].push_back(A[mid]);

    findTree(start, mid - 1, level - 1);
    findTree(mid + 1, end, level - 1);
}

void solution() {
    findTree(0, pow(2, K) - 2, K);

    for (int i = 0; i < K; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << " ";
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> K;

    for (int i = 0; i < pow(2, K) - 1; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}