표현 가능한 이진트리

이진트리를 수로 표현하는 방법은 다음과 같습니다.

이진수를 저장할 빈 문자열을 생성합니다.
주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
문자열에 저장된 이진수를 십진수로 변환합니다.
이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

제한사항
1 ≤ numbers의 길이 ≤ 10,000
1 ≤ numbers의 원소 ≤ 1015

맨 처음 생각한것
모든 값을 탐색해야한다. 왜냐? (빈 노드 뒤에 1이 올수있기 때문에.)
따라서 dfs로 문제를 해결해야하지 않을까?
포화 이진트리이기 때문에 16과 같은 숫자가 들어가더라도 4개의 노드로 이루어진 트리가 아닌 5개로 이루어진 이진트리가 필요함.

문제를 풀다가 생각난 것은 '포화' 이진 트리이기때문에 항상 레벨0의 루트노드는 1이다.(1이 아닌경우 무조건 표현가능하지않기 때문)
따라서 level의 따른 포화이진트리의 크기와 root값이 0인 트리를 확인만 한다면 해결되는 문제다.

코드

import java.lang.Math;
class Solution {
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        for(int i=0;i<numbers.length;i++){
            String binary = Long.toBinaryString(numbers[i]);
            binary= levelNumber(binary);          
            if(binaryTree(binary)){
                answer[i]=1;
            }else{
                answer[i]=0;
            }            
        }
         
      
       
        return answer;
    }
    //포화 이진트리를 만드는 함수
    String levelNumber(String number){
        int length = number.length();
        int level = 0;
        
        while(length!=0){
            level++;
            length=length/2;
        }
        int nodecount=(int)Math.pow(2,level)-1;
       
        number= "0".repeat(nodecount-number.length())+number;
      
        return number;
    }
    //트리확인
    boolean binaryTree(String number){
        if(number.length()==0) return true;
        int mid = number.length()/2;
        String righttree = number.substring(0,mid);
        String lefttree = number.substring(mid+1,number.length());//자기자신을 빼기위한 +1
        if(number.charAt(mid)=='0'){
            return zeroTree(righttree)&&zeroTree(lefttree);
        }
        return binaryTree(righttree)&&binaryTree(lefttree);
    }
    //제로트리 검사
    boolean zeroTree(String number){      
        for(int i=0;i<number.length();i++){
            if(number.charAt(i)=='1')
                return false;
        }
        return true;
    }
    
    
}

제로트리 검사시 모든 양 제로트리를 추적해서 내려갈 필요없이 이미 루트노드가 0이기 떄문에 앞으로 나오는 것의 노드에서 1이 나온다면 이진트리는 표현 불가능하다. 따라서 재귀는 트리확인에서만 하면 충분하다.