Минимизируйте поставки вакцин против коронавируса для N домов, если вакцины достаточно для непосредственных соседей.

Опубликовано: 19 Сентября, 2022

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

Примеры:

Input:

    1

   /

  2   3 

       

         4

         

           5

           

             6

Output: 2
Explanation:
The vaccine kits should be supplied to house numbers 1 and 5.

Input:

    1

   /

  2   3 

Output: 1
Explanation: 
The vaccine kits should be supplied to house number 1.

Подход: Эту проблему можно решить с помощью динамического программирования.

  • Создайте хеш-таблицу, чтобы отслеживать все посещенные узлы.
  • Рекурсивная функция должна возвращать количество непосещенных дочерних узлов ниже.
  • Если узел равен NULL, верните 0. Это будет нашим базовым условием.
  • Создайте переменную-счетчик для хранения количества непосещенных дочерних узлов и инициализируйте ее рекурсивным вызовом для левого и правого дочерних узлов.
    • Если переменная счетчика равна нулю, все дочерние узлы были посещены. Если текущий узел не посещался и не является корневым узлом, мы возвращаем 1, поскольку существует один узел, т.е. текущий узел, который не посещался.
    • Если текущий узел не посещался и переменная счетчика также равна нулю, и если текущий узел является корневым узлом, мы увеличиваем ответ на 1 и возвращаем 1.
    • В противном случае, если переменная счетчика больше нуля, мы помечаем родительский узел, текущий узел и дочерние узлы как посещенные и увеличиваем ответ на 1.

Ниже приведена реализация описанного выше подхода.


Сложность времени: НА).
Вспомогательное пространство: НА)

РЕКОМЕНДУЕМЫЕ СТАТЬИ