[programmers/js] 표현 가능한 이진트리

표현 가능한 이진트리

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

문제 설명

정수 number가 주어질 때, 이 수를 이진 트리로 표현할 수 있는지를 판별해야 합니다.

단, 트리는 포화 이진 트리(모든 노드가 0개 또는 2개의 자식을 가지는 완전한 구조)여야 하며, 다음 규칙을 따릅니다.

• 어떤 노드가 0이라면, 해당 노드를 루트로 하는 서브트리의 모든 노드는 0이어야 한다.
• 표현할 수 있다면 1, 아니라면 0을 반환한다.

풀이

1. 정수를 이진수로 변환합니다. 이때, 포화 이진트리를 만족하지 못하는 경우 앞에 '0'을 추가합니다.

function padToFullBinaryTree(bin) {
    const len = bin.length;
    let fullLen = 1;

    while (fullLen < len) {
        fullLen = fullLen * 2 + 1;
    }

    return bin.padStart(fullLen, '0');
}

2. 분할 정복을 통해 각 노드를 확입니다.

function check(bin) {
    if (bin.length === 1) return 1; // 리프노드는 항상 가능

    // 중간 인덱스를 루트 노드로
    const root = Math.trunc(bin.length / 2);
	
  	// 루트가 0인데 왼쪽/오른쪽 서브트리에 1이 있다면 잘못된 트리다.
    if (bin[root] === '0') {
        if (bin.includes('1')) return 0;
        return 1;
    }
	// 아니라면 재귀적으로 왼쪽과 오른쪽을 확인한다
    const left = bin.slice(0, root);
    const right = bin.slice(root + 1);
    return check(left) && check(right);
}

3. 최종 코드

function solution(numbers) {
    function padToFullBinaryTree(bin) {
        const len = bin.length;
        let fullLen = 1;

        while (fullLen < len) {
            fullLen = fullLen * 2 + 1;
        }

        return bin.padStart(fullLen, '0');
    }

    function check(bin) {
        if (bin.length === 1 && bin[0] === '1') return 1;
        const root = Math.trunc(bin.length / 2);

        if (bin[root] === '0') {
            if (bin.includes('1')) return 0;
            return 1;
        }

        const left = bin.slice(0, root);
        const right = bin.slice(root + 1);
        return check(left) && check(right);
    }

    return numbers.map((n) => {
        const bin = padToFullBinaryTree(n.toString(2));
        return check(bin) ? 1 : 0;
    });
}