표현 가능한 이진트리 [자바]

 

🧫 문제 분석

✔️ 출처

 표현 가능한 이진트리 level 3

 

 

📖 문제

 

포화 이진트리를 만들고 

중앙이 항상 해당 서브트리의 루트인 것을 이용한다.

루트가 0일때 자식 노드가 1이면 불가능판정을 내리면 된다.

 

 

이진트리의 높이 공식은 

2^h - 1 = N

h = Math.ceil(Log2(N + 1));

 

이진트리 오랜만에 풀다보니 잘생각이 안나서 좀 고생했다. 

 

 

 

 

---

🔅 문제 풀이

import java.util.Arrays;

class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        
        for (int i = 0; i < numbers.length; i++) {
            String bit = Long.toBinaryString(numbers[i]);
            int len = bit.length();
            
            int h = (int)Math.ceil((Math.log(len + 1) / Math.log(2)));
            int n = (int)Math.pow(2, h) - 1;
            
            StringBuilder sb =  new StringBuilder();
            for (int j = len; j < n; j++) {
                sb.append('0');
            }
            sb.append(bit);
        
            int[] binTree = Arrays.stream(sb.toString().split(""))
                .mapToInt(Integer::parseInt)
                .toArray();
            
            answer[i] = dfs(binTree, 0, n - 1) ? 1: 0;
            
        }
        return answer;
    }
    
    private boolean dfs(int[] tree, int s, int e) {
        if (s >= e) return true;
        
        int mid = (s + e) / 2;
        
        if (tree[mid] == 0) {
            for (int i = s; i <=e; i++) {
                if (i == mid) continue;
                if (tree[i] == 1) return false;
            } 
        }     
        
        return dfs(tree, s, mid - 1) & dfs(tree, mid + 1, e);
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1.