इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड एक मान रखता है। हमारा कार्य बाइनरी ट्री के दो पत्तों के बीच अधिकतम पथ योग ढूंढने के लिए एक प्रोग्राम बनाना है।
यहां, हमें एक पत्ते नोड से दूसरे पत्ते नोड तक का पथ ढूंढना है जो मानों का अधिकतम योग प्रदान करेगा। यह अधिकतम योग पथ रूट नोड को शामिल कर भी सकता है और नहीं भी।
बाइनरी ट्री एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड में अधिकतम दो चाइल्ड नोड हो सकते हैं। इन्हें लेफ्ट चाइल्ड और राइट चाइल्ड कहा जाता है।
उदाहरण -
आइए एक उदाहरण से इस समस्या को समझते हैं -
इनपुट - //बाइनरी ट्री...
आउटपुट - 24
व्याख्या - पत्ते नोड - 2 से 9 तक का पथ अधिकतम योग देगा जो (2 + 5 + 6 -2 + 4 + 9) = 24 है
इस समस्या को हल करने के लिए, हम ट्री ट्रैवर्सल करेंगे और वर्तमान नोड के लिए लेफ्ट सब-ट्री/राइट सबट्री का अधिकतम योग स्टोर करेंगे। साथ ही, हम अब तक दो पत्ते नोड्स के बीच अधिकतम पथ ढूंढेंगे।
हर नोड के लिए हम उसके सबट्री के लिए अधिकतम संभव पत्ते-से-पत्ते पथ ढूंढेंगे। और फिर इसकी तुलना समग्र अधिकतम पथ से करेंगे और दोनों में से अधिकतम मान को ग्लोबल अधिकतम पथ योग मान में स्टोर करेंगे।
आइए इस समाधान को हमारे उदाहरण से देखें ताकि समाधान बेहतर समझ में आए -
ग्लोबल अधिकतम योग = 6 (पथ 2→5→-1 के लिए)
अब हम 6 को रूट नोड मानकर जांच करेंगे।
लेफ्ट सबट्री में -
पत्ते नोड्स तक पथ का योग 7 और 4 है।
अधिकतम 7 है (पथ 5→2 के लिए)।
राइट सबट्री में -
पत्ते नोड्स तक पथ का योग 5 है पथ (1→-3→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
