[PGM] 2023 KAKAO BLIND RECRUITMENT: Representable Binary Tree (Python)

📅

loading..🐩🐩🐩🐩

https://school.programmers.co.kr/learn/courses/30/lessons/150367↗

Algorithm categories 🔗

Recursion, binary trees.

Problem description 🔗

You are given zero or a positive integer.

Convert it to binary and place it in a binary tree, then determine whether it forms a valid tree.

For example, 9 becomes 1001 in binary, producing the following tree.

This is

not a valid tree

In this problem, a 0 represents a missing node.

The following example converts 7 to binary and places it in a binary tree.

This is a

valid tree

because no child node has an empty parent node.

Return a list containing 1 for each valid tree and 0 otherwise.

Solution 🔗

Convert the given number to binary.
Find the binary string's length and the height of a tree that can contain it. Increase n until 2 to the power of n is at least the length.
Pad the binary string with zeros until its length matches 2 to the power of n.
Write a function to check whether the tree is valid.
The validity-checking function works as follows.
1. Return True if the list has length 0.
2. If the middle element is 0, representing a missing node, but its descendants contain a 1, return False.
3. Otherwise, recursively inspect the first and second halves of the list, checking the left and right subtrees.
Check the tree for each input number, collect the results in a list, and return it.

Code — 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:]) # 재귀적으로 확인

Key points 🔗

How to determine a binary tree's height.
How to check tree validity by recursively checking child nodes.

[PGM] 2023 KAKAO BLIND RECRUITMENT: Representable Binary Tree (Python) | PromleeBlog