[백준 9934번] 완전 이진 트리 (java)

9934번: 완전 이진 트리

중위순회한 결과가 주어지면 트리의 구조를 출력하는 문제이다.
중위순회의 특징을 알면 쉽게 문제를 풀 수 있다. 중위순회한 결과에서 가운데 값은 해당 트리의 루트에 해당한다.
1 - 6 - 4 - 3 - 5 - 2 - 7

즉, 전체 트리에 루트 노드는 3번이다.
그 다음 3을 기준으로 왼쪽(1 - 6 - 4)는 왼쪽 자식 트리를 중위순회한 결과이며, 오른쪽(5 - 2 - 7)은
오른쪽 자식 트리를 중위순회한 결과이다. 각각의 자식 트리도 마찬가지로 가운데 값이 부모노드일 것이다.

1 - 6 - 4    5 - 2 - 7

이런식으로 재귀를 이용하여 문제를 해결하였다.
트리의 높이를 크기로 하는 StringBuffer 배열을 생성하였다.
StringBuffer[] ans = new StringBuffer();
ans[0] : 트리의 첫번째 높이 -> 3
ans[1] : 트리의 두번째 높이 -> 6 2
ans[2] : 트리의 세번째 높이 -> 1 4 5 7

재귀함수의 매개변수로 현재 노드가 트리의 몇층(floor)에 해당하는지를 넣어준 후, 해당하는 노드의 번호를
ans[floor] 문자열 뒤에 추가해준다.

정답코드 :

	import java.io.*;
	public class n09934 {
	static int K;
	static int[] arr;
	static StringBuffer[] ans;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	K = Integer.parseInt(br.readLine());
	arr = new int[(int) Math.pow(2, K) - 1];
	String[] input = br.readLine().split(" ");
	for (int i = 0; i < arr.length; i++)
	arr[i] = Integer.parseInt(input[i]);
	ans = new StringBuffer[K];
	for (int i = 0; i < K; i++)
	ans[i] = new StringBuffer();
	solve(0, arr.length - 1, 0);
	for (int i = 0; i < K; i++)
	bw.write(ans[i].toString() + "\n");
	bw.flush();
	}
	public static void solve(int s, int e, int floor) {
	if (floor == K)
	return;
	int m = (s + e) / 2;
	ans[floor].append(arr[m] + " ");
	solve(s, m - 1, floor + 1);
	solve(m + 1, e, floor + 1);
	}
	}

view raw 9934.java hosted with ❤ by GitHub