[JAVA]BOJ 9934, 완전 이진 트리

inoder로 들어온 완전이진트리를 트리의 모습.. 음 레벨 순회로 각 레벨마다 줄바꿈해서 출력하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ9934 {
    public static void getTree(int[] arr, int start, int end, int level, List<List<Integer>> levels){
        int middle;

        if(start <= end){
            middle = (start + end) / 2;
            levels.get(level).add(arr[middle]); // 자기 자신을 먼저 저장

            getTree(arr, start, middle - 1, level + 1, levels); // 자기자신을 기준으로 왼쪽 순회
            getTree(arr, middle + 1, end, level + 1, levels); // 자기자신을 기준으로 오른쪽 순회
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<List<Integer>> levels = new ArrayList<>();
        StringTokenizer st;
        int n, i, cnt = 1;
        int[] arr;

        // 노드 개수 구하기
        n = Integer.parseInt(br.readLine());
        for(i=0;i<n;i++)
            cnt *=2;
        cnt = cnt - 1;

        // 입력값(inorder결과) 저장하기
        arr = new int[cnt];
        st = new StringTokenizer(br.readLine());
        for (i = 0; i < cnt; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        // 레벨별로 노드를 저장할 리스트 생성
        for (i = 0; i < n; i++)
            levels.add(new ArrayList<>()); // 각 레벨에 해당하는 리스트 생성

        getTree(arr, 0, cnt - 1, 0, levels);

        // 각 레벨별로 출력
        for(i=0;i<n;i++){
            for(int value : levels.get(i))
                System.out.print(value + " ");
            System.out.println();  // 레벨별로 줄바꿈
        }
    }
}

트리를 찾는것 자체는 어렵지 않지만, 출력이 까다롭다.. 리스트를 만들어서 레벨별로 자기자신 노드를 저장해줬다.