Камеры с двоичным деревом - Ежедневное испытание, май

Сегодняшний вопрос от Daily Leetcode Coding Challenge - May Edition. Это жесткий вопрос. Давайте посмотрим на постановку проблемы.

968. Камеры двоичного дерева

Учитывая двоичное дерево, мы устанавливаем камеры на узлы дерева.

Каждая камера в узле может контролировать свою родительскую, саму себя и своих непосредственных дочерних элементов.

Вычислите минимальное количество камер, необходимое для наблюдения за всеми узлами дерева.

Пример:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Понимание проблемы:

Поскольку мы хотим минимизировать количество камер, ясно одно: мы не размещаем камеры в листовом узле. Таким образом, мы можем проследить путь от листа до корня. Это делает DFS наиболее вероятным решением проблемы. Но по мере того, как мы возвращаемся назад, нам нужно обмениваться информацией между узлами, чтобы увидеть, нужна ли текущему узлу камера или нет. Если на предыдущем узле уже есть камера, она нам не нужна. Подводя итог, нам нужно учесть следующее:

Если текущий узел является листовым, то камера нам не нужна.
Если у нас нет камеры на текущем узле, то она нужна родителю.
Если у текущего узла есть камера, то его родительскому узлу камера не нужна.

Мы можем присвоить разные значения для обозначения этих состояний. -1 из детей означает поставить фотоаппарат. 1 от любых детей означает отсутствие камеры.

Реализация кода:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        def dfs(node):
            l=0
            r=0
            if (node.left is None and node.right is None):
                return -1
            if node.left:
                l = dfs(node.left)
            if node.right:
                r = dfs(node.right)
            if(l == -1 or r == -1):
                self.count += 1
                return 1
            if(l == 0 and r == 0):
                return -1
            if(l == 1 or r == 1):
                return 0
        self.count=0
        cams = dfs(root)
        if(cams == -1):
            self.count += 1
        return self.count

Анализ сложности

Сложность времени: O (N) , где N - количество узлов в двоичном дереве.
Сложность пространства: пространство для стеков рекурсивных вызовов, которые могут быть N.

Удачного кодирования !!!

Камеры с двоичным деревом - Ежедневное испытание, май