इस समस्या में, हमें एक बाइनरी ट्री BT दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो बाइनरी ट्री में अधिकतम उप-ट्री योग ढूंढे जैसे कि उप-ट्री भी एक BST हो।
बाइनरी ट्री में एक विशेष शर्त होती है कि प्रत्येक नोड के अधिकतम दो बच्चे हो सकते हैं।
बाइनरी सर्च ट्री एक ट्री है जिसमें सभी नोड्स नीचे उल्लिखित गुणों का पालन करते हैं:
- बाएं उप-ट्री की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से कम होता है।
- दाएं उप-ट्री की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से अधिक या बराबर होता है।
उदाहरण
इनपुट
आउटपुट
32
व्याख्या
यहां, हमारे पास दो उप-ट्री हैं जो BST हैं। उनका योग है,
7 + 3 + 22 = 32 6 + 5 + 17 = 28 अधिकतम = 32।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान ट्री डेटा संरचना को पार करना और फिर प्रत्येक नोड पर जांचना है कि क्या इसके चाइल्ड नोड्स बाइनरी सर्च ट्री बना सकते हैं या नहीं। यदि हम BST में योगदान देने वाले सभी नोड्स का योग ढूंढते हैं और फिर पाए गए सभी BSTSum में से अधिकतम वापस करते हैं।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <bits/stdc++.h>
using namespace std;
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int findMin(int a, int b){
if(a > b)
return b;
return a;
}
struct Node {
struct Node* left;
struct Node* right;
int data;
Node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
struct treeVal{
int maxVal;
int minVal;
bool isBST;
int sum;
int currMax;
};
treeVal CalcBSTSumTill(struct Node* root, int& maxsum){
if (root == NULL)
return { -10000, 10000, true, 0, 0 };
if (root->left == NULL && root->right == NULL) {
maxsum = findMax(maxsum, root->data);
return { root->data, root->data, true, root->data, maxsum };
}
treeVal LeftSTree = CalcBSTSumTill(root->left, maxsum);
treeVal RightSTree = CalcBSTSumTill(root->right, maxsum);
treeVal currTRee;
if (LeftSTree.isBST && RightSTree.isBST && LeftSTree.maxVal < root->data && RightSTree.minVal > root->data) {
currTRee.maxVal = findMax(root->data, findMax(LeftSTree.maxVal, RightSTree.maxVal));
currTRee.minVal = findMin(root->data, findMin(LeftSTree.minVal, RightSTree.minVal));
maxsum = findMax(maxsum, RightSTree.sum + root->data + LeftSTree.sum);
currTRee.sum = RightSTree.sum + root->data + LeftSTree.sum;
currTRee.currMax = maxsum;
currTRee.isBST = true;
return currTRee;
}
currTRee.isBST = false;
currTRee.currMax = maxsum;
currTRee.sum = RightSTree.sum + root->data + LeftSTree.sum;
return currTRee;
}
int CalcMaxSumBST(struct Node* root){
int maxsum = -10000;
return CalcBSTSumTill(root, maxsum).currMax;
}
int main(){
struct Node* root = new Node(10);
root->left = new Node(12);
root->left->right = new Node(7);
root->left->right->left = new Node(3);
root->left->right->right = new Node(22);
root->right = new Node(6);
root->right->left = new Node(5);
root->right->left->right = new Node(17);
cout<<"The maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST is "<<CalcMaxSumBST(root);
return 0;
}
आउटपुट
The maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST is 32
