완전 이진 트리

문제 정보

• 사이트 : 백준 알고리즘 사이트
• 문제 번호 : 9934
• 문제 분류 : binary search
• 난이도 : silver 1

문제 풀이

내가 짠 코드

• 아래와 같이 트리의 깊이를 하나씩 늘려가면서 규칙을 찾아보았더니 배열을 반으로 나누었을 때 가운데 부분이 부모 노드였다.
• 이를 이용해서 이진 탐색 방식을 변형해서 문제를 풀었다.
  

public class Main {
    private static int num,n;
    private static int[] arr;
    private static ArrayList<Integer>[] level;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        num = (int) Math.pow(2,n) - 1;
        arr = new int[num];
        level = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            level[i] = new ArrayList<>();
        }

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < num; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        binarySearch(0,num-1,0);

        for (int i = 0; i < n; i++) {
            for (Integer integer : level[i]) {
                System.out.print(integer+" ");
            }
            System.out.println();
        }
        br.close();
    }

    public static void binarySearch(int low, int high, int height){
        if(height == n){
            return;
        }
        int mid = (low + high) / 2;
        level[height].add(arr[mid]);
        binarySearch(low, mid-1, height+1);
        binarySearch(mid+1, high, height+1);
    }
}

문제 출처

• 백준 완전 이진 트리

썸네일 출처

Image by storyset on Freepik