समस्या कथन
एक बाइनरी ट्री को देखते हुए जिसमें प्रत्येक नोड तत्व में एक संख्या होती है। कार्य एक पत्ती के नोड से दूसरे में न्यूनतम संभव योग खोजना है।
उदाहरण
ऊपर के पेड़ में न्यूनतम उप पथ -6 इस प्रकार है:(-4) + 3 + 2 + (-8) + 1
एल्गोरिदम
विचार रिकर्सिव कॉल में दो मान बनाए रखना है -
- वर्तमान नोड के अंतर्गत रूट किए गए सबट्री के लिए न्यूनतम रूट टू लीफ पथ योग
- पत्तियों के बीच न्यूनतम पथ योग
- प्रत्येक विज़िट किए गए नोड X के लिए, हमें X के बाएँ और दाएँ उप-वृक्षों में न्यूनतम रूट टू लीफ योग खोजना होगा। फिर X के डेटा के साथ दो मान जोड़ें, और वर्तमान न्यूनतम पथ योग के साथ योग की तुलना करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int data;
struct node *left;
struct node *right;
} node;
node *newNode(int data) {
node *n = new node;
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
int getMinPath(node *root, int &result) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return root->data;
}
int leftSum = getMinPath(root->left, result);
int rightSum = getMinPath(root->right, result);
if (root->left && root->right) {
result = min(result, root->data + leftSum + rightSum);
return min(root->data + leftSum, root->data + rightSum);
}
if (root->left == NULL) {
return root->data + rightSum;
} else {
return root->data + leftSum;
}
}
int getMinPath(node *root) {
int result = INT_MAX;
getMinPath(root, result);
return result;
}
node *createTree() {
node *root = newNode(2);
root->left = newNode(3);
root->right = newNode(-8);
root->left->left = newNode(5);
root->left->right = newNode(-4);
root->right->left = newNode(1);
root->right->right = newNode(10);
return root;
}
int main() {
node *root = createTree();
cout << "Minimum sum path = " << getMinPath(root) << endl;
return 0;
} जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
आउटपुट
Minimum sum path = -6