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