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

dfs 문제이다. 

 

* 중위 순회의 흐름 차순은 L - Root - R 순이다. 

 

#접근방법

1. 답을 저장할 이차원 벡터와 데이터를 저장할 일차원 벡터 생성.   
2. 시작 포인터와 끝 포인터를 지정하여 그 중간점을 매개변수로 전달하여 왼쪽 자식 노드의 끝까지 들어간다.
3. level 이 입력받은 깊이의 수와 동일하다면 return.
4. 해당 레벨에 위치의 이차원벡터에 현재 담고있는 데이터의 값을 담아준다. 
5. 우측 자식 노드로 재귀함수를 호출한다. 

#include <iostream>
#include <vector>
using namespace std; 
int n; 
vector <vector<int>> v;
void dfs(int s, int e, int level, vector<int>& data) {
	if (level==n) return; 	
	int mid = (s + e) / 2;
	dfs(s, mid - 1, level + 1, data);//왼쪽
	v[level].push_back(data[mid]); 
	dfs(mid + 1, e, level + 1, data); //오른쪽
}

int main() {
	cin >> n;
	vector <int> data((1 << n) - 1); 
	int i; 
	for (i = 0; i < (1 << n) - 1; i++){
		cin >> data[i]; 
	}
	int s = 0; 
	int e = --i; 
	v.resize(n); 
	dfs(s, e, 0, data);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < v[i].size(); j++) {
			cout << v[i][j] << " ";
		}cout << endl; 
	}
}

 

9934번: 완전 이진 트리