Найти все пути с четной суммой в заданном двоичном дереве поиска

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

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

Примеры:

Input:

Img-Btree

Output:
Even sum Paths are:
1st) 1 -> 19 -> 4 -> 9 -> 7 = sum(40) 
2nd) 1 -> 19 -> 4 -> 9 -> 13 -> 18 -> 16 = sum(80)
3rd) 1 -> 19 -> 25 -> 35 = sum(68)
4th) 1 -> 19 -> 25 -> 23 = sum(80)
Explanation: When we start traversing form root node to the leaf node then we have different path are (1, 19, 4, 9, 7), (1, 19, 4, 9, 13, 18, 16), (1, 19, 25, 35), (1, 19, 25, 23) and (1, 19, 4, 2, 3). And after finding the sum of every path we found that all are even. Here we found one path as odd which are 1 -> 19 -> 4 -> 2 -> 3 = sum(29).

Input:    2
            /  
         1     3
Output: No path
Explanation: There is no path which has even sum.

Подход: Задачу можно решить с помощью стека, исходя из следующей идеи:

Traverse the whole tree and keep storing the path in the stack. When the leaf is reached check if the sum of the path is even or not.

Выполните шаги, указанные ниже, чтобы реализовать подход:

  • Возьмите один стек (скажем, путь ) для хранения текущего пути .
  • Рекурсивно пройти по дереву и на каждой итерации:
    • Сохраните сумму всех узлов на этом пути (скажем, sum ) и также сохраните данные этого узла в пути .
    • Траверс для левого ребенка.
    • Траверс для правого ребенка.
    • Если конечный узел достигнут, проверьте, является ли сумма пути четной или нечетной.
  • Вернуть все такие пути.

Ниже приведен код для лучшего понимания:

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

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