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

---

1. 코드

def solution(numbers):
    def bit_length_decision(n):
        if n == 1:
            return 1
        prev = 1
        for i in range(2, 51):
            curr = pow(2, i) - 1
            if prev < n <= curr:
                return curr

    def add_zero_bit(bit):
        length = bit_length_decision(len(bit))
        return bit.zfill(length)

    def dfs(bit):
        if len(bit) == 1:
            return bit

        mid = len(bit) // 2
        left = bit[:mid]
        right = bit[mid+1:]

        l_child = dfs(left)
        r_child = dfs(right)

        if bit[mid] == '0' and (l_child == '1' or r_child == '1'):
            return False
        elif not l_child or not r_child:
            return False
        else:
            return bit[mid]

    answer = []
    for num in numbers:
        bi = bin(num)[2:]
        result = add_zero_bit(bi)

        if result[len(result) // 2] == '0':
            answer.append(0)
            continue

        if dfs(result):
            answer.append(1)
        else:
            answer.append(0)

    return answer

2. 후기

루트 노드를 제외한 부모 노드는 0값을 가지려면 자식 노드들 모두 0을 가져야한다. DFS 방식으로 아래서부터 위로 올라가기 때문에 부모-왼쪽자식, 부모-오른쪽자식끼리 비교하여 자식이 1을 가질 경우 False를 반환한다.

3. DFS 후위 순회

DFS 호출 순서 출력

def dfs(bit):
    if len(bit) == 1:
        return bit

    mid = len(bit) // 2
    left = bit[:mid]
    right = bit[mid+1:]

    # LRN(후위 순회)
    l_child = dfs(left)   # L
    r_child = dfs(right)  # R

    print(f'left={l_child}, right={r_child}, mid={bit[mid]}')
    return bit[mid]

print(dfs('1327465f8a9ebdc'))
"""
left=1, right=2, mid=3
left=4, right=5, mid=6
left=3, right=6, mid=7
left=8, right=9, mid=a
left=b, right=c, mid=d
left=a, right=d, mid=e
left=7, right=e, mid=f
f
"""