문제

풀이

1. 십진수를 이진수 문자열로 바꾼다.
2. 0을 채워서 포화이진트리로 바꾼다.
3. 부모 노드가 0이고 자식노드가 1이면 불가능한 경우이다.

   ---

코드

class Solution {
    public int[] solution(long[] numbers) {
            int[] answer = new int[numbers.length];
            for (int i = 0; i < numbers.length; i++) {
                if(numbers[i]==0L){
                    answer[i]=0;
                    continue;
                }
                String bin = toBin(numbers[i]);
                if (check(bin)) {
                    answer[i] = 1;
                } else answer[i] = 0;
            }
            return answer;
        }

        static String toBin(long num) {
            StringBuilder sb = new StringBuilder();
            while (num > 0) {
                long remainder = num % 2;
                sb.insert(0, remainder);
                num >>= 1;
            }
            int len = sb.length();
            int treeHeight = (int) Math.ceil(Math.log(len + 1) / Math.log(2));
            int totalNodeCnt = (int) Math.pow(2, treeHeight) - 1;
            for (int i = 0; i < totalNodeCnt - len; i++) sb.insert(0, 0);
            return sb.toString();
        }

        static boolean check(String bin) {
            if (bin.length()==1 || checkAllZero(bin)) {
                return true;
            }

            int mid = bin.length() >> 1;

            boolean res1 = check(bin.substring(0, mid));
            boolean res2 = check(bin.substring(mid + 1));
            if (bin.charAt(mid) == '0' &&
                    res1
                    && res2) {
                return false;
            }

            return res1 && res2;
        }

        static boolean checkAllZero(String str){
            for(char c:str.toCharArray()){
                if(c!='0')return false;
            }
            return true;
        }
}

#트리