Вывести все пути от корня к листу с указанной суммой в двоичном дереве

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

Примеры:

Input: K = 22
                5
              /    
            4       8
           /       /  
          11      13   4
         /           / 
        7    2       5   1

Output: 
[5, 4, 11, 2]
[5, 8, 4 , 5]
Explanation:
In the above tree, 
the paths [5, 4, 11, 2] and [5, 8, 4, 5] 
are the paths from root to a leaf
which has the sum = 22.

Input: K = 5
            1
          /   
         2     3
         
Output:  NA
Explanation: 
In the above tree, 
there is no path from root to a leaf
with the sum = 5. 

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

1. Поместите текущее значение узла в стек.
2. Если текущий узел является конечным узлом. Проверьте, равны ли данные в листовом узле оставшейся target_sum .
   а . если оно равно, поместите значение в стек и добавьте весь стек в наш список ответов.
   б. в противном случае нам не нужен этот путь от корня до листа.
3. Рекурсивно вызовите левое поддерево и правое поддерево, вычитая текущее значение узла из target_sum .
4. Извлеките самый верхний элемент из стека, потому что мы выполнили операцию с этим узлом.

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

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