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

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

Примеры:

Input:
             0
           /
        0
      /
    0  0
Output: 1
Explanation:
             0
           /
        0  <———- Camera
      /
   0   0
In the above tree, the nodes which are bold are the nodes having the camera. Placing the camera at the level 1 of the Tree can monitor all the nodes of the given Binary Tree.
Therefore, the minimum count of camera needed is 1.

Input:
             0
           /
        0
      /
    0 
     
       0
Output: 2

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

• Если значение равно 1 , узел отслеживается.
• Если значение равно 2 , узел не отслеживается.
• Если значение равно 3 , узел имеет камеру.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, count , чтобы хранить минимальное количество камер, необходимых для наблюдения за всеми узлами данного дерева.
• Создайте функцию, скажем, dfs(root) , которая берет корень данного дерева и возвращает статус каждого узла, независимо от того, была ли размещена камера или нет, или узел контролируется любым другим узлом, имеющим камеру, и выполните следующие шаги. :
  • Если значение узла равно NULL , верните 1 , так как узел NULL всегда отслеживается.
  • Рекурсивно вызывать левое и правое поддеревья и сохранять возвращаемое ими значение в переменных L и R .
  • Если значение L и R равно 1 , то верните 2 из текущего рекурсивного вызова, поскольку текущий корневой узел не отслеживается.
  • Если значение L или R равно 2 , увеличьте значение count на 1 , так как один из левых и правых узлов не отслеживается, и верните 3 .
  • В противном случае верните 1 .
• Вызовите вышеуказанную рекурсивную функцию из корня, и если возвращаемое ею значение равно 2 , то увеличьте значение count на 1 .
• После выполнения вышеуказанных шагов выведите значение count как результирующее количество камер.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(H), где H — высота данного дерева.