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

문제

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

내가 이해한 방법은, 이진트리 -> 숫자 표현 가능한지를 구하는 것보다 숫자 -> 이진트리로 나타냈을 때 해당 이진트리가 존재할 수 있는지?를 구해봄

노드 순서

제일 어려웠던 점이 노드의 순서였는데,

• 이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.
  부모 / 왼쪽 자식 / 오른쪽 자식이 있다고 가정했을 때
  어느 관점에서 보아도 부모는 항상 왼쪽 자식보다는 늦게 오고, 오른쪽 자식보다는 먼저 온다는 말을 저렇게 표현한듯...
  이 말인 즉슨 제일 최상단의 루트 노드의 순서는 전체 노드의 개수/2가 된다는 뜻이고, 각 서브트리의 루트 노드의 순서는 항상 짝수가 됨

포화 이진트리 만들기

십진수 -> 이진수로 변환했을 때 그 길이가 노드의 개수가 됨
포화 이진트리가 되기 위해서는 노드의 개수가 항상 1,3,7,...2^n-1개를 유지해야 되기 때문에

• 앞에 0을 삽입해서 길이를 2^n-1로 맞춰줘야 함
• 당연히 0을 중간에 삽입할 수는 없음(그러면 다른 수가 되어버리기 때문에)

이제 중요한 건 어떤 조건에서 이진트리가 되지 못하는가?인데
처음에 생각한 건 각 서브트리의 루트 노드가 0일 때였는데,
128 - '10000000'

• 8자리이기 때문에 2^n-1을 맞추기 위해서 '000000010000000'로 바꿔줘야 하고, 이렇게 되면 최상단 루트 노드만 1이고 나머지는 모두
  더미 노드가 됨 - 이 경우도 전혀 문제 없음
• 꼭 최하단 노드에서만 더미 노드를 추가할 수 있는 게 아님

본인의 부모 노드가 0,즉 더미 노드일 때 자식이 1 - 이 경우는 불가능(애초에 더미 노드를 추가하는 이유는, 128과 같이 포화 이진트리를 만들기 위해서이기 때문)

• 부모가 1일 때 더미 0 추가 or 부모가 0일 때(더미일때) 더미 0 추가 이 두 가지 경우밖에 될 수가 없음

그래서 top-down 방식으로 본인의 자식 노드를 조사하면서, 본인이 0인데 자식이 1인 경우는 표현할 수 없는 이진트리 가 됨

코드

function solution(numbers) {
    const s = []
   for(const number of numbers){
       let string = number.toString(2)
       let i = string.length
       let sum = 0
       while(i>=1){
           sum++
           i /= 2
       }
       let result = 0
       string = string.padStart(2**sum-1,'0')
       const a = findChildren([Math.floor(string.length/2)+1],sum-1,string)
       if(a === true){
           s.push(1)
       }else{
           s.push(0)
       }
       }
    //자릿수에서 가장 가까운 수를 알아야함
   function findChildren(arr, sum, string) {
    if (!arr.length) {
        return false;
    }
    if (sum <= 0) {
        return true
    }
    const result = [];
    for (let root of arr) {
        const [left, right] = [root - (2**(sum-1)), root + (2**(sum-1))];
        if (string[root - 1] == 0 && string[left - 1] == 1) {
            return false;
        }
        if (string[root - 1] == 0 && string[right - 1] == 1) {
            return false;
        }
        result.push(left);
        result.push(right);
    }
    return findChildren([...result], sum - 1, string); // Note the "return" here
}
        return s
}