Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में टू सम IV - इनपुट एक BST है


मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक लक्ष्य मान है; हमें जांचना है कि क्या BST में दो तत्व मौजूद हैं जिनका योग दिए गए लक्ष्य के बराबर है या नहीं।

इसलिए, यदि इनपुट जैसा है:

C++ में टू सम IV - इनपुट एक BST है

तो आउटपुट True होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • एक सरणी v परिभाषित करें
  • एक फ़ंक्शन inorder() परिभाषित करें, जो root लेगा,
    • यदि root null है, तो वापस लौटें
    • inorder(root का बायां)
    • root का मान v में डालें
    • inorder(root का दायां)
  • एक फ़ंक्शन findnode() परिभाषित करें, जो k लेगा,
    • n := v का आकार
    • i < j होने तक लूप चलाएं:
      • t := v[i] + v[j]
      • यदि t == k, तो:
        • true वापस करें
      • यदि t < k, तो:
        • i को 1 से बढ़ाएं
      • अन्यथा:
        • j को 1 से घटाएं
    • false वापस करें
  • मुख्य विधि से निम्नलिखित करें:
    • inorder(root)
    • सरणी v को सॉर्ट करें
    • findnode(k) वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#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; 
} 
class Solution { 
public: 
    vector<int> v; 
    void inorder(TreeNode* root){ 
        if (root == NULL || root->val == 0) 
            return; 
        inorder(root->left); 
        v.push_back(root->val); 
        inorder(root->right); 
    } 
    bool findnode(int k){ 
        int n = v.size(), i = 0, j = n - 1; 
        while (i < j) { 
            int t = v[i] + v[j]; 
            if (t == k) 
                return true; 
            if (t < k) 
                i++; 
            else 
                j--; 
        } 
        return false; 
    } 
    bool findTarget(TreeNode* root, int k){ 
        inorder(root); 
        sort(v.begin(), v.end()); 
        return findnode(k); 
    } 
}; 
int main(){ 
    Solution ob; 
    vector<int> v = {5,3,6,2,4,NULL,7}; 
    TreeNode *root = make_tree(v); 
    cout << (ob.findTarget(root, 9)); 
}

इनपुट

{5,3,6,2,4,NULL,7},9

आउटपुट

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

    मान लीजिए हमारे पास एक बाइनरी ट्री की रूट है, हमें किसी भी उपट्री का अधिकतम योग ज्ञात करना है जो बाइनरी सर्च ट्री (BST) भी हो। यदि इनपुट है - तो आउटपुट 20 होगा, यह चयनित BST में सभी नोड्स का योग है। हल करने के चरण Data नामक एक संरचना बनाएं, जिसमें sz, maxVal, minVal, ok, sum सदस्य हों। एक इनिशि

  1. C++ में BST के दो नोड्स के बीच अधिकतम तत्व C++ में BST के दो नोड्स के बीच अधिकतम तत्व

    समस्या कथन N तत्वों का एक ऐरे और दो पूर्णांक A, B दिए गए हैं जो दिए गए ऐरे से संबंधित हैं। arr[0] से arr[n-1] तक तत्व डालकर एक बाइनरी सर्च ट्री बनाएं। कार्य A से B तक के पथ में अधिकतम तत्व ढूंढना है। उदाहरण यदि ऐरे है {24, 23, 15, 36, 19, 41, 25, 35} तो हम BST को निम्नानुसार बना सकते हैं: यदि हम

  1. C++ में N फैक्टोरियल के योग के अंतिम दो अंक ढूंढना C++ में N फैक्टोरियल के योग के अंतिम दो अंक ढूंढना

    यहां हम देखेंगे कि अंतिम दो अंक कैसे प्राप्त करें। N फैक्टोरियल के योग का इकाई स्थान अंक और दहाई स्थान अंक। यदि N=4 है, तो यह 1! + 2! + 3! + 4! = 33 होगा। इसलिए इकाई स्थान 3 और दहाई स्थान 3 है। परिणाम 33 होगा। 10 के बाद, दहाई स्थान भी 0 रहेगा। N=10 और अधिक के लिए, यह 00 होगा। हम N=1 से 10 तक के फै