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

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

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

Примеры:

Input: Tree in the image below, list = {3, 6, 8}

Output: Yes
Explanation: There exists a downward path in the given Binary Tree, having all the elements of the linked list in the same order.

Input: Tree in the image below, list = {1, 2, 5, 7}
 

Output: Yes

Подход: Данная проблема может быть решена с помощью DFS Traversal of the Binary tree. Во время обхода DFS, если какой-либо узел двоичного дерева равен заголовку связанного списка, можно вызвать рекурсивную функцию isPathUntil() , чтобы рекурсивно проверить, существуют ли другие элементы связанного списка как путь от этого узла. . Если полный связанный список был пройден, существует допустимый требуемый путь, поэтому верните true . В противном случае вернуть false . Выполните следующие шаги, чтобы решить данную проблему:

  • Объявите функцию, скажем, isSubPathUtil(root, head) и выполните следующие шаги в этой функции:
    • Если корень равен NULL , верните false .
    • Если заголовок равен NULL, верните true.
    • Если значение текущего корневого узла совпадает со значением текущего заголовка LL, то рекурсивно вызовите isSubPathUtil(root->left, head->next) и isSubPathUtil(root->right, head->next) и если значение, возвращенное одним из этих рекурсивных вызовов, равно true, то вернуть true. В противном случае вернуть false .
  • Объявите функцию, скажем, isSubPath(root, head) и выполните следующие шаги в этой функции:
    • Если корень равен NULL , верните false .
    • Если заголовок равен NULL , верните true.
    • Если значение текущего корневого узла совпадает со значением текущего заголовка LL, то рекурсивно вызовите isSubPath(root->left, head->next) и isSubPath(root->right, head->next) и если значение, возвращенное одним из этих рекурсивных вызовов, равно true, то вернуть true. В противном случае рекурсивно возвращайте значение для isSubPath(root->left, head) и isSubPath(root->right, head) .
  • После вышеуказанных шагов, если значение, возвращаемое функцией isSubPath(root, head) , равно true , выведите Yes . В противном случае выведите Нет .

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

Временная сложность: O(N * M), где N = количество узлов в двоичном дереве и M = количество узлов в связанном списке.
Вспомогательное пространство: O(1)

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