[Programmers] 표현 가능한 이진트리 - Python

이진수로 변환하고 -> 이진수를 표현하는 포화 이진 트리를 만들고 -> 포화 이진 트리를 탐색 하는 총 3가지의 로직을 구현해주면 되는 문제이다. 

트리 란 비선형 자료구조들 중에서 자료 간 (= 노드) 계층 관계를 가진 자료구조이다. 

포화 이진 트리란 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 노드로 차있는 트리이다. 또한 각 노드들이 2개의 자식 노드들을 가지며, 홀수 개의 자식 노드를 가질 수 없다. 즉, 자식 노드가 0개이거나 2개이다. 

# 포화 이진 트리를 탐색
def check_tree(binary):
    root = len(binary) // 2  # mid
    if root == 0:  # leaf node
        return True
    if binary[root] == '0':
        if '1' not in binary:
            return True
        return False
    return check_tree(binary[:root]) and check_tree(binary[root + 1:])


def make_binary(n):
    reversed_binary = []  # 1. 이진수 저장 빈 문자열
    while n != 1:
        reversed_binary.append(str(n % 2))
        n //= 2
    reversed_binary.append("1")
    binary = "".join(reversed_binary[::-1])  # 나머지를 뒤집어서 이진수 만들기
    # 2. 포화이진트리 만들기 (2**0 + 2**1 + 2**2 + 2**3 ..)
    max_binary_tree = 1
    while max_binary_tree < len(binary):
        max_binary_tree = (max_binary_tree + 1) * 2 - 1
    binary = "0" * (max_binary_tree - len(binary)) + binary  # 부족한만큼 0 추가하기
    return binary


def solution(numbers):
    answer = []  # result

    for n in numbers:
        binary = make_binary(n)
        if check_tree(binary):  # True
            answer.append(1)
        else:
            answer.append(0)

    return answer

# 올바른 트리의 경우 : 부모 0 - 자식 0 는 가능
# 부모 0 - 자식 1 는 틀림
# 부모 1 - 자식 0 가능
# 부모 1 - 자식 1 가능