프로그래머스 LV3 표현가능한 이진트리

https://school.programmers.co.kr/learn/courses/30/lessons/150367
트리만 보면 겁을 먹는 자기 자신을 반성하며 2시간 동안 고민하여 풀었다.

결국 완전한 이진트리이기 때문에 받아오는 숫자의 노드 개수를 1,3,7,15 이렇게 맞춰줘야했다.

    public static long findDepth(long num) {
        long depth = 0;
        long plus = 1;
        long count = 0;
        while (num > depth) {
            depth = depth + plus;
            plus*=2;
            count++;
        }
        depth = 0;
        plus = 1;
        while (count > depth) {
            depth = depth + plus;
            plus *= 2;
        }
        return depth;
    }

즉 받아오는 숫자에 따라 만들어야 하는 트리 노드 개수를 가져왔고

  public static long[] digit (long num,long depth) {
        Stack <Long> d = new Stack<>();
        while (num > 1) {
            d.add(num % 2);
            num /= 2;
        }

        d.add(num);
        int size =d.size();
        if(size < depth) {
            for (int i = 0; i < (int)depth - size; i++) {
                d.add((long)0);
            }
        }
        long [] arr = new long [(int)depth];
        for (int i = 0; i < depth; i++) {
            arr[i] = d.pop();
        }
        return arr;
    }

십진수를 이진수로 만든다음 채워야할 노드 개수가 부족하다면 추가해주는 방식을 취했다.

마지막으로 분할정복을 통해서 더미노드가 아닌 노드들을 판단하면서 노드가 1이 아니라면 FALSE를 리턴하는 방식으로 짰다.
여기서 예외케이스가 하나 발생하는데 바로 0을 계속해서 추가하여 더미노드의 서브트리도 전부 더미 노드인 노드들이 생긴다는 점이었다. 즉 판단하는 노드가 0이라도 노드의 서브트리가 더미노드로 되어있는 서브트리였다면 FALSE를 리턴하지 않았어야 했다.

    public static void check (int start, int last, long [] arr) {
        int mid =  (start+last) / 2 ;
        if(arr[mid] == 0) {
            for(int i = start ; i <= last ; i++) {
                if (arr[i] == 1) {
                     isTree = false;
                     return;
                }
            }
        }
        if (last - start == 2) {
            return;
        }
        check(start,mid-1,arr);
        check(mid+1,last,arr);
    }