इस समस्या में, हमें एक बाइनरी ट्री दिया जाता है जिसमें प्रत्येक नोड में एक मान होता है। हमारा काम एक बाइनरी ट्री की दो पत्तियों के बीच अधिकतम पथ योग खोजने के लिए एक प्रोग्राम बनाना है।
यहां, हमें एक लीफ नोड से दूसरे लीफ नोड के लिए पथ फॉर्म ढूंढना होगा जो अधिकतम मूल्यों को प्रदान करेगा। इस अधिकतम योग पथ में रूट नोड शामिल नहीं हो सकता है।
बाइनरी ट्री एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड में अधिकतम दो चाइल्ड नोड हो सकते हैं। इन्हें बायां बच्चा और दायां बच्चा कहा जाता है।
उदाहरण -
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं -
इनपुट - // बाइनरी ट्री…
आउटपुट - 24
स्पष्टीकरण − लीफ नोड -2 से 9 तक का पथ अधिकतम योग देगा जो कि है (2 + 5 + 6 -2 + 4 + 9 ) =24
इस समस्या को हल करने के लिए, हम ट्री ट्रैवर्सल करेंगे और वर्तमान नोड के लिए लेफ्ट सब-ट्री/राइट सबट्री के लिए अधिकतम योग स्टोर करेंगे। साथ ही, हम अब तक दो लीफ नोड्स के बीच अधिकतम पथ पाएंगे।
प्रत्येक नोड के लिए, हम इसके उपप्रकारों के लिए अधिकतम संभव पत्ती से पत्ती पथ पाएंगे। और फिर इसकी तुलना समग्र अधिकतम पथ से करें और अधिकतम दोनों मानों को वैश्विक अधिकतम पथ योग मान में संग्रहीत करें।
आइए समाधान को बेहतर ढंग से समझने के लिए इस समाधान को हमारे उदाहरण से देखें -
वैश्विक अधिकतम योग =6 (पथ 2→5→-1 के लिए)
अब हम 6 को रूट नोड के रूप में लेने के लिए जाँच करेंगे।
बाएं सबट्री में -
लीफ नोड्स तक पथ का योग 7 और 4 है।
अधिकतम 7 है (पथ 5→2 के लिए)।
दाएँ उपप्रकार में -
लीफ नोड्स तक पथ का योग पथ के लिए 5 है (1rarr;-3rarr;7) जो एक संभव तरीका है।
नहीं, लीफ नोड्स के बीच पथ का योग है -
पत्ती से जड़ तक का अधिकतम योग (6) बाएँ उपवृक्ष में + जड़ + पत्ती से जड़ तक का अधिकतम योग (6) दाएँ उप वृक्ष में =7 + 6 + 5 =18.
वैश्विक अधिकतम पथ योग(6) की तुलना में, नया वैश्विक अधिकतम पथ योग =18.
उदाहरण
दो लीफ नोड्स के बीच अधिकतम पथ योग खोजने के लिए प्रोग्राम -
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
struct Node* insertNode(int data){
struct Node* node = new(struct Node);
node->data = data;
node->left = node->right = NULL;
return (node);
}
int max(int a, int b)
{ return (a >= b)? a: b; }
int maxPathSumLeaf(struct Node *root, int &maxSum){
if (root==NULL) return 0;
if (!root->left && !root->right) return root->data;
int leftSubTree = maxPathSumLeaf(root->left, maxSum);
int rightSubTree = maxPathSumLeaf(root->right, maxSum);
if (root->left && root->right){
maxSum = max(maxSum, leftSubTree + rightSubTree + root->data);
return max(leftSubTree, rightSubTree) + root->data;
}
return (!root->left)? rightSubTree + root->data: leftSubTree + root->data;
}
int main(){
struct Node *root = insertNode(-2);
root->left = insertNode(6);
root->right = insertNode(4);
root->left->left = insertNode(5);
root->left->right = insertNode(1);
root->left->left->left = insertNode(2);
root->left->left->right = insertNode(-1);
root->left->right->left = insertNode(-3);
root->left->right->left->left = insertNode(7);
root->right->left = insertNode(9);
root->right->right = insertNode(3);
int maxSum = INT_MIN;
maxPathSumLeaf(root, maxSum);
cout<<"Max pathSum of between two leaf nodes for the given binary tree is "<<maxSum;
return 0;
} आउटपुट
Max pathSum of between two leaf nodes for the given binary tree is 24