C++のバイナリツリーにすべてのk-sumパスを出力します

この問題では、二分木と数Kが与えられ、パス内のノードの合計がkに等しいツリー内のすべてのパスを出力する必要があります。

ここで、ツリーのパスは、ツリーの任意のノードから開始し、任意のノードで終了することができます。パスは常にルートノードからリーフノードに向かう必要があります。ツリーのノードの値は、正、負、またはゼロにすることができます。

問題を理解するために例を見てみましょう-

K =5

出力 −

1 3 1
3 2
1 4

この問題を解決するために、各ノードをツリーのルートノードとして扱い、値を合計してKに達する一時的なルートから他のノードへのパスを見つけます。

パスのすべてのノードをベクトルに格納し、kに評価される合計値を確認します。

例

アルゴリズムの実装を示すプログラム-

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node *left,*right;
   Node(int x){
      data = x;
      left = right = NULL;
   }
};
void printPath(const vector<int>& v, int i) {
   for (int j=i; j<v.size(); j++)
      cout<<v[j]<<"\t";
   cout<<"\n";
}
void findKSumPath(Node *root, vector<int>& path, int k) {
   if (!root)
      return;
   path.push_back(root->data);
   findKSumPath(root->left, path, k);
   findKSumPath(root->right, path, k);
   int f = 0;
   for (int j=path.size()-1; j>=0; j--){
      f += path[j];
      if (f == k)
         printPath(path, j);
   }
   path.pop_back();
}
int main() {
   Node *root = new Node(1);
   root->left = new Node(3);
   root->left->left = new Node(1);
   root->left->right = new Node(2);
   root->right = new Node(4);
   root->right->right = new Node(7);
   int k = 5;
   cout<<"Paths with sum "<<k<<" are :\n";
   vector<int> path;
   findKSumPath(root, path, k);
   return 0;
}

Paths with sum 5 are −
1 3 1
3 2
1 4