Задача: 968. Binary Tree Cameras
Сложность: hard
Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми.
Верните минимальное количество камер, необходимых для наблюдения за всеми узлами дерева.
Пример:
Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
👨💻 Алгоритм:
1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.
2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.
3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.
😎 Решение:
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
def solve(node):
if not node:
return 0, 0, float('inf')
L = solve(node.left)
R = solve(node.right)
mL12 = min(L[1], L[2])
mR12 = min(R[1], R[2])
d0 = L[1] + R[1]
d1 = min(L[2] + mR12, R[2] + mL12)
d2 = 1 + min(L[0], mL12) + min(R[0], mR12)
return d0, d1, d2
return min(solve(root)[1:])
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Вам дан корень бинарного дерева. Мы устанавливаем камеры на узлы дерева, где каждая камера на узле может наблюдать за своим родителем, собой и своими непосредственными детьми.
Верните минимальное количество камер, необходимых для наблюдения за всеми узлами дерева.
Пример:
Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
👨💻 Алгоритм:
1⃣Рекурсивное решение (solve):
Для каждого узла определите три состояния:
- [State 0] Строгое поддерево: все узлы ниже этого узла покрыты, но не сам узел.
- [State 1] Нормальное поддерево: все узлы ниже и включая этот узел покрыты, но на этом узле нет камеры.
- [State 2] Установленная камера: все узлы ниже и включая этот узел покрыты, и на этом узле установлена камера.
Рассчитайте эти состояния для левого и правого поддеревьев.
2⃣Рассчёт состояний:
Чтобы покрыть строгое поддерево, дети этого узла должны находиться в состоянии 1.
Чтобы покрыть нормальное поддерево без установки камеры на этом узле, дети этого узла должны находиться в состояниях 1 или 2, и по крайней мере один из этих детей должен быть в состоянии 2.
Чтобы покрыть поддерево при установке камеры на этом узле, дети могут находиться в любом состоянии.
3⃣Минимальное количество камер:
Запустите функцию solve на корневом узле и верните минимальное значение между состояниями 1 и 2.
😎 Решение:
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
def solve(node):
if not node:
return 0, 0, float('inf')
L = solve(node.left)
R = solve(node.right)
mL12 = min(L[1], L[2])
mR12 = min(R[1], R[2])
d0 = L[1] + R[1]
d1 = min(L[2] + mR12, R[2] + mL12)
d2 = 1 + min(L[0], mL12) + min(R[0], mR12)
return d0, d1, d2
return min(solve(root)[1:])
Ставь 👍 и забирай 📚 Базу знаний