In tất cả các đường dẫn từ gốc, với một tổng được chỉ định trong cây nhị phân trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân và một tổng S. Và chúng ta phải tìm đường dẫn bắt đầu từ gốc đến bất kỳ nút nào của cây, cho tổng bằng tổng đã cho.

Đầu vào

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

Để tìm ra giải pháp cho vấn đề này, chúng ta cần tìm trình duyệt được đặt trước của cây nhị phân. Và sau đó tìm đường dẫn đến tổng đã cho.

Ví dụ

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

Đầu ra

Các đường dẫn với tổng đã cho là -

4 10
4 3 7