Given: binary tree (tree algorithm is written by hand). Number S. It is necessary to find a sequence of nodes (only from top to bottom or vice versa) in a binary tree, the sum of which is equal to S.

For example: there is a binary tree, and the number S = 9. example

Solution: 3 + 6, 4 + 5, 9.

ps it is desirable that this be a separate class that has access to the binTree class

#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(); };

    2 answers 2

    The task draws on the Olympics, I am writing an idea.

    The decision will be made using the dynamics on the tree.

    For each node in the tree we will get a list of values. Initialization - in sheets {0, Value}. Recalculation from the bottom above. The value for the node is recalculated like this (current vertex 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();

    I specifically write pseudocode, since there can be any structure on the specifics of the problem (list vector set bitset), etc.

    For each vertex where in the list there is an S will be a response sequence that ends in it. It can be restored like this. The sequence is uniquely defined by the initial and final element. I will return only the initial ones.

     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; }

    Something of the order of O (N ^ 2 log N) is difficult. You can optimize, but if you display all the sequences, then there may be about the same. Further implementations / optimization you know better.

    • as I did not quite understand the "scheme" of the first code ... Could you, describe in more detail. - Andrey
    • and what exactly is not clear? - pavel
    • For each node we find its sum of values: Node + All that to the right + All that to the left? - Andrey
    • If so, then this is the wrong decision. From each node can be lowered either to the left or to the right. (This is the condition of the problem) - Andrey
    • updated. By the way, if you completely score on speed, you can simply go through the upper and lower points. - pavel

    Actually everything turned out much easier. In the node structure added:

     list<pair<int, list<int>>> lSumNodes;

    to count all possible amounts. Also added a member of the class:

     list<list<int>> m_lSum;

    where saved all the sequences of nodes, the sum of which equals the desired number.

    Well, all processing takes place in three class methods:

     void binTree::CulSum(int S) { SumNode(m_pRoot); SearchSum(m_pRoot, S); ShowSum(); }

    Counting all possible amounts for all nodes:

     void binTree::SumNode(Node * X) { if (X != NULL) { SumNode(X->pLeft); SumNode(X->pRight); if (X->pLeft != NULL) { for (auto i : X->pLeft->lSumNodes) { i.second.push_front(X->Value); auto tmpPair = make_pair(i.first + X->Value, i.second); X->lSumNodes.push_back(tmpPair); } } if (X->pRight != NULL) { for (auto i : X->pRight->lSumNodes) { i.second.push_front(X->Value); auto tmpPair = make_pair(i.first + X->Value, i.second); X->lSumNodes.push_back(tmpPair); } } list<int> tmpList; tmpList.push_front(X->Value); auto tmp = make_pair(X->Value, tmpList); X->lSumNodes.push_back(tmp); } }

    Search for the required amount:

     void binTree::SearchSum(Node * X, int S) { if (X != NULL) { for (const auto i : X->lSumNodes) if (i.first == S) m_lSum.push_back(i.second); SearchSum(X->pLeft, S); SearchSum(X->pRight, S); } }

    Method solution, though clumsy, but do not care. Everyone who has not passed by - thanks!