Произведение пути от корня к листу, равное заданному числу

Опубликовано: 3 Декабря, 2021

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

Например, в приведенном выше дереве существует три пути от корня к листу со следующими продуктами.

  • 240 -> 10 - 8 - 3
  • 400 -> 10 - 8 - 5
  • 40 -> 10 - 2 - 2
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы начать рекурсивный обход дерева и разделить значение текущего узла от продукта, если оно делится при повторении вниз, и проверить, равно ли продукт 1, когда вы достигнете конечного узла текущего пути дерева. .

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

Выход :

 ДА

Сложность времени: O (n)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.