C++ में बाइनरी ट्री में अधिकतम योग BST

मान लीजिए हमारे पास एक बाइनरी ट्री की रूट है, हमें किसी भी उपट्री का अधिकतम योग ज्ञात करना है जो बाइनरी सर्च ट्री (BST) भी हो।

यदि इनपुट है -

तो आउटपुट 20 होगा, यह चयनित BST में सभी नोड्स का योग है।

हल करने के चरण

Data नामक एक संरचना बनाएं, जिसमें sz, maxVal, minVal, ok, sum सदस्य हों। एक इनिशियलाइज़र परिभाषित करें जो (sz, minVal, maxVal, ok) लेता है और sum को 0 सेट करता है
ret := 0
solve() नामक एक विधि परिभाषित करें जो ट्री रूट लेती है
यदि नोड शून्य है या नोड का मान 0 है, तो (0, INF, -INF, true) के साथ नया Data वापस करें
left := solve(node का बायाँ), right := solve(node का दायाँ)
Data प्रकार का एक उदाहरण curr बनाएं, curr.ok := false
यदि node->val >= right.minVal तो curr वापस करें
यदि node->val <= left.maxVal तो curr वापस करें
यदि left.ok और right.ok दोनों सत्य हैं, तो curr.sum, ret, curr.sz, curr.ok, curr.maxVal, curr.minVal अद्यतन करें
मुख्य विधि से: ret := 0, solve(root) कॉल करें, ret वापस करें

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class TreeNode { 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data) { 
        val = data; 
        left = NULL; 
        right = NULL; 
    } 
}; 

void insert(TreeNode **root, int val) { 
    queue<TreeNode*> q; 
    q.push(*root); 
    while(q.size()) { 
        TreeNode *temp = q.front(); 
        q.pop(); 
        if(!temp->left) { 
            if(val != NULL) temp->left = new TreeNode(val); 
            else temp->left = new TreeNode(0); 
            return; 
        } else { 
            q.push(temp->left); 
        } 
        if(!temp->right) { 
            if(val != NULL) temp->right = new TreeNode(val); 
            else temp->right = new TreeNode(0); 
            return; 
        } else { 
            q.push(temp->right); 
        } 
    } 
} 

TreeNode *make_tree(vector<int> v) { 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; i < v.size(); i++) insert(&root, v[i]); 
    return root; 
} 

struct Data { 
    int sz; 
    int maxVal; 
    int minVal; 
    bool ok; 
    int sum; 
    Data() {} 
    Data(int a, int b, int c, bool d) { 
        sz = a; minVal = b; maxVal = c; ok = d; sum = 0; 
    } 
}; 

class Solution { 
public: 
    int ret = 0; 
    Data solve(TreeNode* node) { 
        if (!node || node->val == 0) 
            return Data(0, INT_MAX, INT_MIN, true); 
        Data left = solve(node->left); 
        Data right = solve(node->right); 
        Data curr; 
        curr.ok = false; 
        if (node->val >= right.minVal) return curr; 
        if (node->val <= left.maxVal) return curr; 
        if (left.ok && right.ok) { 
            curr.sum = node->val + left.sum + right.sum; 
            ret = max(curr.sum, ret); 
            curr.sz = 1 + left.sz + right.sz; 
            curr.ok = true; 
            curr.maxVal = max(node->val, right.maxVal); 
            curr.minVal = min(node->val, left.minVal); 
        } 
        return curr; 
    } 
    int maxSumBST(TreeNode* root) { 
        ret = 0; 
        solve(root); 
        return ret; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}; 
    TreeNode *root = make_tree(v); 
    cout << (ob.maxSumBST(root)); 
    return 0; 
}

इनपुट

{1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}