Произведение пути от корня к листу, равное заданному числу
Для двоичного дерева и числа возврат будет истинным, если дерево имеет такой путь от корня к листу, что произведение всех значений на этом пути равно заданному числу. Если такой путь не может быть найден, возврат будет ложным.
Например, в приведенном выше дереве существует три пути от корня к листу со следующими продуктами.
- 240 -> 10 - 8 - 3
- 400 -> 10 - 8 - 5
- 40 -> 10 - 2 - 2
Подход: идея состоит в том, чтобы начать рекурсивный обход дерева и разделить значение текущего узла от продукта, если оно делится при повторении вниз, и проверить, равно ли продукт 1, когда вы достигнете конечного узла текущего пути дерева. .
Ниже представлена реализация описанного выше подхода:
Выход :
ДА
Сложность времени: O (n)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.