문제
깊이 K인 완전 이진 트리의 중위 순회 결과가 주어질 때, 각 레벨별 노드를 출력한다.
입력
첫째 줄에 트리의 깊이 K가 주어진다 (1 이상 10 이하). 둘째 줄에 2^K - 1개의 건물 번호가 중위 순회 순서로 주어진다.
출력
K줄에 걸쳐 각 레벨의 노드 번호를 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 2 3 4 5 6 7 | 4 2 6 1 3 5 7 |
풀이
중위 순회 배열에서 중간 원소가 현재 레벨의 루트라는 성질을 이용하여 재귀적으로 트리를 복원한다.
- 2^K - 1개의 노드를 배열에 저장한다
- K개의 레벨별 리스트를 생성한다
- search(start, end, depth) 재귀 함수로 배열의 중간값을 현재 깊이의 레벨 리스트에 추가한다
- 왼쪽 절반과 오른쪽 절반에 대해 깊이를 증가시켜 재귀 호출한다
- 레벨별 리스트를 순서대로 출력한다
핵심 아이디어: 중위 순회에서 배열의 중앙 원소가 루트이므로, 분할 정복으로 각 레벨의 노드를 복원할 수 있다.
코드
package day549;
import java.io.*;
import java.util.*;
public class Day537BOJ9934완전이진트리 {
static int k;
static int[] arr;
static List<ArrayList<Integer>> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
arr = new int[(int) Math.pow(2, k) - 1];
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
list = new ArrayList<>();
for (int i = 0; i < k; i++) {
list.add(new ArrayList<>());
}
search(0, arr.length - 1, 0);
for (int i = 0; i < k; i++) {
for (int j : list.get(i)) {
sb.append(j).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
static void search(int start, int end, int depth) {
if (depth == k) {
return;
}
int mid = (start + end) / 2;
list.get(depth).add(arr[mid]);
search(start, mid - 1, depth + 1);
search(mid + 1, end, depth + 1);
}
}복잡도
- 시간: O(N)
- 공간: O(N)