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

문제 링크

코드

def solution(numbers):
    binarys = list(map(lambda x: bin(x)[2:], numbers))
    full_binarys = list(map(insert_dummy, binarys))
    return list(map(lambda x: 1 if validate(x) else 0, full_binarys))
    
    
def insert_dummy(s):
    l = len(s)
    x = 1
    while x - 1 < l:
        x *= 2
    return "0" * (x - l - 1) + s


def validate(tree):
    if "1" not in tree:
        return True
    
    mid = len(tree) // 2
    if tree[mid] != "1":
        return False
    
    return validate(tree[:mid]) and validate(tree[mid + 1:])

리뷰

• 문제의 핵심은 더미 노드 아래에 실제 노드가 있으면 안된다는 것이다
• 따라서 먼저 포화 트리를 만든 후, 루트 노드(중간값)을 확인하고, 1이면 좌우 서브트리에 대해 다음과 같은 과정을 반복했다