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

depth 별 노드들 저장해야함

static List<ArrayList<Integer>> list;

리스트에 값 넣어주기

• 중위순회한 순서로 노드들의 입력값이 들어옴
• 중간에 있는 값이 해당 depth의 노드인것을 파악해야함!

static void search(int start, int end, int depth) {
        //종료
        if(depth == k) {
            return;
        }

        //확장
        int mid = (start + end) / 2; // 중위 순회(inorder traverse) 순서의 중간점
        //가운데 값이 해당 depth에 속하는 노드가 됨

        list.get(depth).add(nodes[mid]); // 중간값이 그 depth의 top

        search(start, mid - 1, depth + 1);

        search(mid + 1, end, depth + 1);
    }

전체 풀이

import java.io.*;
import java.util.*;

public class Main {
    static int k;
    static int[] nodes;
    static List<ArrayList<Integer>> list = new ArrayList<>(); // depth에 맞게 노드를 저장하기 위한 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();

        // 완전 이진 트리의 노드개수 = 2^k-1개
        int N = (int) Math.pow(2, k) - 1;
        nodes = new int[N];

        for (int i = 0; i < N; i++) {
            nodes[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < k; i++) {
            list.add(new ArrayList<>());
        }

        search(0, N - 1,0); // 해당 depth 별로 노드들을 list에 넣는 작업

        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; // 중위 순회(inorder traverse) 순서의 중간점

        list.get(depth).add(nodes[mid]); // 중간값이 그 depth에 속함

        search(start, mid - 1, depth + 1); // 앞에 먼저해야 순서 보장!

        search(mid + 1, end, depth + 1);
    }
}

풀이

문제에서 출력형식이 depth 별 노드를 출력해줬어야 했음
완전이진트리의 중위순회에 메커니즘에 대해 잘 생각해보면 해당 depth의 노드를 알 수 있음
순회 중간에 있는 값이 해당 depth의 노드!!