C++에서 이진 트리의 모든 k-sum 경로 인쇄

이 문제에서 이진 트리와 숫자 K가 주어지고 경로에 있는 노드의 합이 k인 트리의 모든 경로를 인쇄해야 합니다.

여기서 트리의 경로는 트리의 모든 노드에서 시작하여 모든 노드에서 끝날 수 있습니다. 경로는 항상 루트 노드에서 리프 노드로 향해야 합니다. 트리 노드의 값은 양수, 음수 또는 0일 수 있습니다.

문제를 이해하기 위해 예를 들어 보겠습니다 -

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