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

문제

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

 

해설

완전이진트리의 탐색에 대한 문제였음 완전 이진 트리에서 inorder의 경우 절반을 자르면 루트 노드가 나온다는 특징을 이용해야 하는 문제

코드

#include <bits/stdc++.h>
using namespace std;
 
int k, num[1028];
vector<int> ret[14];
 
void go(int first, int last, int level)
{
  if (last < first)
  {
    return;
  }
  if (first == last)
  {
    ret[level].push_back(num[first]);
    return;
  }
 
  int mid = (first + last) / 2;
  ret[level].push_back(num[mid]);
  go(first, mid - 1, level + 1);
  go(mid + 1, last, level + 1);
}
 
int main()
{
  cin >> k;
  int last = (int)pow(2, k) - 1;
  for (int i = 0; i < last; i++)
  {
    cin >> num[i];
  }
 
  go(0, last - 1, 1);
  for (int i = 1; i <= k; i++)
  {
    for (int n : ret[i])
    {
      cout << n << " ";
    }
    cout << "\n";
  }
}