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

처음에 문제를 조금 헷갈려서 어려운 문제였다.

 

사실 문제 자체를 해결하는 로직자체는 어렵지 않다.

 

1. 수를 이진수로 바꿔서 트리형식으로 펼치기

2. 이진트리가 될 수 있게 더미노드를 추가하기

3. 더미노드가 추가된 이진트리가 올바른 트리인지 확인하기

 

 

1번에서 조금 헤맸다. 만약 더미노드를 추가한다면 0을 앞뒤로 넣는다는건데 어떻게 얼마나 넣어야하는지 헷갈렸다.

 

두가지를 보자.

 

1. 더미노드를 활용해서 포화이진트리를 만들어야 한다.

2. 수가 변하면 안된다.

 

1번은 스스로 잘 생각해냈다. 포화이진트리가 되려면 2**n-1개의 크기 즉 트리의 크기가 1,3,7,15,31,63 ... 식의 배열을 따라야 한다. 처음 이해가 안되었던 점은 그렇다면 0을 어디에 붙이냐였다.

 

2번 부분에서 이를 확인할 수 있었다. 0이 만약 뒤에 붙는다면 수 자체의 크기가 변하게 되므로 0을 무조건 앞에만 붙여야 했다.

 

따라서 수를 이진수로 변화시키고 길이가 2**n-1을 만족시키게 0을 앞에다 붙여둔 후 트리가 올바른지 확인하면 된다.

 

 

const isZeroTree = (str) => str.indexOf("1")===-1 ? true : false

const isTree = (str) => {

    if(str.length===1) return 1
    const rootIdx = ~~(str.length/2)
    const [before,root,after] = [str.slice(0,rootIdx),str[rootIdx],str.slice(rootIdx+1)]
    if (root==="0") return isZeroTree(str) ? 1 : 0
    
    return isTree(before) && isTree(after)
}

function solution(numbers) {
    const ret = numbers.map(number => {
        const binary = number.toString(2)
        console.log(binary)
        const n = binary.length.toString(2).length
      
        const str =  "0".repeat(2**n-1 - binary.length) + binary
        // console.log(str)
        return isTree(str)
    })
    return ret
}