Сложность: 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 {
func minCameraCover(_ root: TreeNode?) -> Int {
let ans = solve(root)
return min(ans[1], ans[2])
}
func solve(_ node: TreeNode?) -> [Int] {
if node == nil {
return [0, 0, 99999]
}
let L = solve(node?.left)
let R = solve(node?.right)
let mL12 = min(L[1], L[2])
let mR12 = min(R[1], R[2])
let d0 = L[1] + R[1]
let d1 = min(L[2] + mR12, R[2] + mL12)
let d2 = 1 + min(L[0], mL12) + min(R[0], mR12)
return [d0, d1, d2]
}
}Ставь 👍 и забирай 📚 Базу знаний