23.07.11 Today’s Leetcode

863. All Nodes Distance K in Binary Tree (medium)

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:

        def help(node, dis, check=-1):
            if not node:
                return []
            if node.val == check:
                return []
            if dis < 0:
                return []
            if dis == 0:
                return [node.val]
            
            temp = []
            temp += help(node.left, dis - 1, check)
            temp += help(node.right, dis - 1, check)
            return temp

        route = None
        def find(cur, his):
            nonlocal route
            if not cur:
                return
            if cur.val == target.val:
                route = his[:]
                return

            his.append(cur)
            find(cur.left, his)
            find(cur.right, his)
            his.pop()

        find(root, [])

        route.append(target)
        res = []
        prev = -1
        for i in range(len(route) - 1, -1, -1):
            p = k - len(route) + 1 + i
            # print(route[i].val, p)
            res += help(route[i], p, prev)
            prev = route[i].val
        
        # print(res)
        return res
            

표현 가능한 이진트리

링크

import math

def solution(numbers):
    res = []
    
    def to_bin(k):
        res = ''
        while k:
            k //= 2
            res += '0' if k % 2 == 0 else '1'
        return res
    
    def help(p):
        m = len(p)
        if m <= 1:
            return True
        for i in range(1, m - 1):
            if p[i] == '0':
                continue
            a = help(p[:i])
            b = help(p[i + 1:])
            if a and b:
                return True
        return False
        
    
    for elem in numbers:
        binary = to_bin(elem)
        print(binary)
        
        # len(b) == 2 ** n - 1, n is Integer
        a = math.log(len(binary) + 1, 2)
        
        # len('0' + b) == 2 ** n - 1, n is Integer
        b = math.log(len(binary) + 2, 2)
        
        value = 0
        if a == int(a):
            value |= help(binary)
        if b == int(b):
            value |= help('0' + binary)
        
        res.append(value)
    
    print(res)
        
    return res