Как найти суммы последовательных узлов в бинарном дереве?

Дано: бинарное дерево (алгоритм дерева написан вручную). Число S. Нужно найти последовательность узлов (только с вверху вниз или наоборот) в бинарном дереве, сумма которых равна S
Например: есть бинарное дерево, а число S = 9.
Решение: 3+6, 4+5, 9.
п.с. желательно, что бы это был отдельный класс, который имел доступ к классу binTree
#pragma once class binTree { protected: struct Node { int Value; Node * pLeft; Node * pRight; Node * pParent; Node(int x) :Value(x), pLeft(NULL), pRight(NULL), pParent(NULL) {} }; Node * m_pRoot; void InoderTreeWalk(Node * x); Node * TreeSuccessor(Node *x); Node * TreeMin(Node * x); public: binTree(); ~binTree(); virtual void TreeInsert(int k); Node * TreeSearch(Node * X, int k); void ShowTree(); int Root(); };

Ответ

Задача тянет на олимпиадную, пишу идею.
Решение будет сделано с помощью динамики по дереву.
Для каждого узла в дереве заведём список значений. Инициализация - в листах {0, Value}. Пересчёт снизу вверху. Значение для узла пересчитывается примерно так (текущая вершина U):
for (auto left : U->left->list) U->list.add(left + U->Value); for (auto right: U->left->right) U->list.add(right+ U->Value); U->add(U->Value); U->list->unique();
Я специально пишу псевдокодом, т.к. там может быть любая структура от специфики задачи (list vector set bitset) и т.д.
Для каждой вершины, где в списке есть S будет последовательность ответ, которая заканчивается в ней. Её можно восстановить примерно так. Последовательность однозначно задаётся начальным и конченым элементом. Я верну только начальные.
list fun(Tree *U, int S){ S -= U->Value;
list tmp; if (S == 0) tmp.add(U);
if (U->left->list.contains(S)) tmp.add(fun(U->left,S); if (U->rigth->list.contains(S)) tmp.add(fun(U->rigth,S); return tmp; }
Сложно что-то порядка O(N^2 log N). Оптимизировать можно, но если выводить все последовательности то их может быть примерно столько же. Дальнейшие реализации/оптимизации вам виднее.