इस समस्या में, हमें एक बाइनरी ट्री और एक योग S दिया गया है। और हमें रूट से ट्री के किसी भी नोड तक का पथ ढूंढना है, जो दिए गए योग के बराबर योग देता है।
इनपुट
योग = 14 आउटपुट: पथ: 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
