Минимизируйте поставки вакцин против коронавируса для N домов, если вакцины достаточно для непосредственных соседей.
Гик разработал эффективную вакцину от коронавируса и хочет, чтобы каждый из 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.
Ниже приведена реализация описанного выше подхода.
Сложность времени: НА).
Вспомогательное пространство: НА)