✅ Решение задачи 968

Time: O(n)
Space: O(n)

💡 Идея
🟦Естественно, размещение камер на всех узлах — это лишнее, поэтому мы стремимся размещать камеры стратегически, в идеале на родителях листовых узлов, а не на самих листьях

🟦Это приводит нас к подходу снизу вверх (постпорядковый DFS) с использованием системы состояний, чтобы определить, какое действие следует предпринять на каждом уровне

🟦Реализуем функцию dfs, которая возвращает:
➖-1 — если узлу нужна камера
➖ 0 — если узел охвачен камерой
➖ 1 — если у узла есть камера

🟦Обходим дерево, используя метод обратного поиска в глубину:
➖рекурсивно вычисляем статус левого и правого поддеревьев

➖если какому-либо ребенку нужна камера (-1) , помещаем камеру в текущий узел: увеличиваем счетчик и возвращаем 1

➖если у какого-либо дочернего узла есть камера (1) , текущий узел будет покрыт — возвращаем 0

➖если оба дочерних узла покрыты и не имеют камер, то этому узлу она нужна — возвращаем -1

🟦После выполнения обхода, если корню по-прежнему нужна камера, мы увеличиваем счетчик еще раз

👩‍💻 Java Algo | #solution968