[lv3] 표현 가능한 이진트리

https://school.programmers.co.kr/learn/courses/30/lessons/150367#

 

 

 

1. 입력 전처리

 

{1,3,7,15,31,63}는 각각 높이가 1 ~ 6인 포화 이진 트리의 노드 개수이다.

 

주어진 입력을 2진법으로 변환했을 때, 비트(= 노드)개수가 모자라다면 그만큼 앞에 0(= 더미 노드)을 채워준다.

 

이는 포화 이진 트리를 만드는 과정이다.

 

e.g.)

2 -> 01(2) -> 001(2)

 

 

2. 가능한 해인지 판별

 

true인 조건은 다음과 같다. (0 : 더미 노드, 1 : 더미가 아닌 노드)

 

- 루트 노드는 반드시 1이어야 한다.

- 자식 노드가 0이라면, 부모 노드는 0 or 1이어야 한다.

- 자식 노드가 1이라면, 부모 노드는 1이어야 한다.

 

재귀를 통해, 한 번이라도 위 조건에 맞지 않으면 false로 처리한다.

 

import java.util.*;

class Solution {
    public int[] solution(long[] numbers) {
        // long 범위 내에서 가능한 포화 이진 트리 노드 개수
        int[] bits = {1,3,7,15,31,63};
        int[] answer = new int[numbers.length];

        for(int i=0; i<numbers.length; i++) {

            // 이진수로 표현했을 때, 모자란 길이 만큼 앞에 '0'을 채움
            String bit = Long.toBinaryString(numbers[i]);

            for(int j=0; j<bits.length; j++) {
                int len = bit.length();

                if(len == bits[j]) {
                    break;
                }

                else if(len < bits[j]) {
                    int zero = bits[j] - len;
                    while(zero-- > 0) {
                        bit = "0" + bit;
                    }
                    break;
                }
            }

            answer[i] = reclu(0, bit.length() - 1, '1', bit)? 1 : 0;
        }

        return answer;
    }

    // p : 현재 탐색 중인 서브 트리의 부모 노드 값 - root는 반드시 1이어야 하므로, 처음엔 1로 가정
    static boolean reclu(int l, int r, char p, String bit) {

        // 리프 노드 조건
        if(l == r)
            return bit.charAt(l) == '0' || (bit.charAt(l) == '1' && p == '1');

        int root = (r + l) / 2;
        char rBit = bit.charAt(root);

        // 중간 노드 조건
        if(p == '0' && rBit == '1')
            return false;

        // 서브 트리 탐색
        return reclu(l, root - 1, rBit, bit) && reclu(root + 1, r, rBit, bit);
    }
}