C++의 이진 트리에 지정된 합계를 사용하여 루트의 모든 경로를 인쇄합니다.

이 문제에서 우리는 이진 트리와 합 S가 주어집니다. 그리고 루트에서 시작하여 주어진 합과 동일한 합을 제공하는 트리의 임의의 노드까지의 경로를 찾아야 합니다.

입력

Sum = 14
Output : path : 4 10
4 3 7

이 문제에 대한 해결책을 찾으려면 이진 트리의 선주문 순회를 찾아야 합니다. 그런 다음 주어진 합계가 되는 경로를 찾습니다.

예시

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int key;
   struct Node *left, *right;
};
Node* insertNode(int key){
   Node* temp = new Node;
   temp->key = key;
   temp->left = temp->right = NULL;
   return (temp);
}
void printPathsUtilSum(Node* curr_node, int sum, int
sum_so_far, vector<int> &path){
   if (curr_node == NULL)
      return;
   sum_so_far += curr_node->key;
   path.push_back(curr_node->key);
   if (sum_so_far == sum ){
      for (int i=0; i<path.size(); i++)
         cout<<path[i]<<"\t";
      cout<<endl;
   }
   if (curr_node->left != NULL)
      printPathsUtilSum(curr_node->left, sum,
   sum_so_far, path);
   if (curr_node->right != NULL)
      printPathsUtilSum(curr_node->right, sum,
   sum_so_far, path);
   path.pop_back();
}
void pathWithSum(Node *root, int sum){
   vector<int> path;
   printPathsUtilSum(root, sum, 0, path);
}
int main (){
   Node *root = insertNode(4);
   root->left = insertNode(10);
   root->right = insertNode(3);
   root->right->left = insertNode(7);
   root->right->right = insertNode(1);
   root->left->left = insertNode(8);
   root->left->right = insertNode(6);
   int sum = 14;
   cout<<"Paths with the given sum are : "<<endl;
   pathWithSum(root, sum);
   return 0;
}

출력

주어진 합계를 가진 경로는 -

4 10
4 3 7