[PGM] 2023 KAKAO BLIND RECRUITMENT・表現可能な二分木 (Python)

def solution(numbers):
    answer = []
    for s in numbers:
        binnum, height = bin(s)[2:], 0  # 주어진 수를 이진수로 변환
        while 2 ** height <= len(binnum):  # 이진수의 길이가 2의 n승이 되도록 높이를 구함
            height += 1
        binnum = binnum.zfill(2 ** height - 1) # 이진수의 길이가 2의 n승이 되도록 0을 채움
        answer.append(1 if check(binnum) else 0 )
    return answer
 
def check(lst): # 이진 트리가 온전한 지 확인하는 함수
    n = len(lst) // 2
    if n == 0:  # 리스트의 길이가 1이면 True
        return True
    elif lst[n] == "0" and ("1" in lst): # 빈 노드이지만 자식 노드에 1이 있는 경우 False 
        return False
    else: 
        return check(lst[:n]) and check(lst[n + 1:]) # 재귀적으로 확인