C++ में सबसे बड़ा BST सबट्री - अधिकतम नोड्स वाला BST खोजें

समस्या विवरण

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उसका सबसे बड़ा सबट्री ढूंढना है जहां सबसे बड़ा का अर्थ है सबसे अधिक नोड्स वाला सबट्री।

उदाहरण के लिए, यदि इनपुट इस तरह का ट्री है:

तो आउटपुट 3 होगा, क्योंकि इस मामले में सबसे बड़ा BST सबट्री हाइलाइट किया गया है।

समाधान दृष्टिकोण

पोस्ट-ऑर्डर ट्रैवर्सल के साथ जानकारी पास करना:

एक संरचना Data परिभाषित करें जिसमें चार मान हों: size, maxVal, minVal, और ok (बूलियन)
solve(TreeNode* node):
- यदि नोड null है, तो Data(0, अनंत, -अनंत, true) लौटाएं
- left := solve(बाएं), right := solve(दाएं)
- curr.ok := false
- यदि नोड का मान >= right.minVal, तो curr लौटाएं
- यदि नोड का मान <= left.maxVal, तो curr लौटाएं
- यदि left.ok और right.ok दोनों true हैं:
  - curr.sz := 1 + left.sz + right.sz
  - curr.ok := true
  - curr.maxVal := max(नोड का मान, right.maxVal)
  - curr.minVal := min(नोड का मान, left.minVal)
- यदि curr.ok true है, तो ret = max(ret, curr.sz) अपडेट करें और curr लौटाएं
मुख्य विधि से: ret := 0, solve(root), ret लौटाएं

C++ कार्यान्वयन

#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; 
    Data(){} 
    Data(int a, int b, int c, bool d){ 
        sz = a; 
        minVal = b; 
        maxVal = c; 
        ok = d; 
    } 
}; 

class Solution { 
public: 
    int ret; 
    
    Data solve(TreeNode* node){ 
        if (!node) 
            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.sz = 1 + left.sz + right.sz; 
            curr.ok = true; 
            curr.maxVal = max(node->val, right.maxVal); 
            curr.minVal = min(node->val, left.minVal); 
        } 
        if (curr.ok) 
            ret = max(ret, curr.sz); 
        return curr; 
    } 
    
    int largestBSTSubtree(TreeNode* root){ 
        ret = 0; 
        solve(root); 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {10,5,15,1,8,NULL,7}; 
    TreeNode *root= make_tree(v); 
    cout << (ob.largestBSTSubtree(root)); 
    return 0;
}

इनपुट

[10,5,15,1,8,null,7]