[트리] 백준 9934 완전 이진 트리

9934번: 완전 이진 트리

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

 

# 코드

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

public class Main {
    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));
        StringBuilder sb = new StringBuilder();
        
        // 완전 이진 트리의 깊이 K
        k = Integer.parseInt(br.readLine());
        
        // 완전 이진 트리의 노드 개수 = 2^k-1개
        arr = new int[(int) Math.pow(2, k) - 1];

        // 입력값을 배열에 삽입
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // depth에 맞게 노드를 저장하기 위한 list
        list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(new ArrayList<>());
        }

        // 탐색
        search(0,arr.length - 1,0);

        // 출력을 위해 StringBuilder에 쌓기
        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;

        // depth에 맞게 노드 삽입
        list.get(depth).add(arr[mid]);

        // 왼쪽 노드 (시작부터 중간 - 1 까지)
        search(start, mid - 1, depth + 1);
        // 오른쪽 노드 (중간 + 1 부터 끝까지)
        search(mid + 1, end, depth + 1);
    }
}

 

코드와 주석은 아래 블로그를 참고했다.

(Java) 백준 9934 - 완전 이진 트리