Количество строго возрастающих и убывающих путей в направленном двоичном дереве

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

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

Примечание. Путь начинается с корня и заканчивается на любом конце.

Примеры:

Input: N = 6
tree =             6
                 /        
              4             7
                         /    
                5      6       8
Output: 10 8
Explanation: For the above binary tree, the strictly increasing paths are :
    All the paths consisting of a single node are = 6.
    The paths containing two nodes are: 4->5, 7->8, 6->7 = 3. 
    The paths containing three nodes are: 6->7->8 = 1. 
    Hence, the count of strictly increasing paths is 6 + 3 + 1 = 10.
For the above binary tree, the strictly decreasing paths are:
    All the paths consisting of a single node are = 6.
    The paths containing two nodes are: 6->4, 7->6 = 2.
    Hence, the count of strictly decreasing paths is 6 + 2 = 8.

Input: N = 5
tree                 15
                     /         
                   8            
                   
                     2
                  /    
               13     9
Output: 7 8
Explanation: 
For the above binary tree, the strictly increasing paths are:
    All the paths consisting of a single node are = 5.
    The paths containing two nodes are: 2->9, 2->13 = 2.
    Hence, the count of strictly increasing paths is 5 + 2 = 7.
For the above binary tree, the strictly decreasing paths are:
    All the paths consisting of a single node are = 5.
    The paths containing two nodes are:15->8, 8->2 = 2.
    The paths containing three nodes are: 15->8->2 = 1.
    Hence, the count of strictly decreasing paths is 5 + 2 + 1 = 8.

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

If a path starting from any node u is strictly increasing and its value is greater than the value of its parent (say v), then all the strictly increasing paths starting from u are also strictly increasing paths when the starting node is v. The same is true in case of strictly decreasing paths.

Из приведенного выше наблюдения проблема может быть решена с помощью рекурсии. Выполните следующие шаги, чтобы решить проблему:

  • Используйте рекурсивную функцию для обхода дерева, начиная с корня, и для каждого узла возвращайте количество строго возрастающих и строго убывающих путей от этого узла.
  • В каждой рекурсии:
    • Проверьте, увеличивается или уменьшается путь от текущего узла к дочернему (левому или правому).
    • Вызовите рекурсивную функцию для дочернего элемента .
    • Добавьте количество возрастающих или убывающих путей к общему количеству, если путь от текущего узла к дочернему увеличивается или уменьшается соответственно.
  • Возвращает окончательный счет увеличения или уменьшения пути, полученного для корня.

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

Временная сложность: O(N)
Вспомогательное пространство: O(N)

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