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

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


बाइनरी ट्री दिया गया है। ऐसा उपसमुच्चय ढूंढें जिसका योग अधिकतम हो और जिसमें कोई दो नोड्स सीधे जुड़े न हों (पैरेंट-चाइल्ड नहीं)।

उदाहरण ट्री के लिए अधिकतम योग 11 है।

समाधान दृष्टिकोण (मेमोइजेशन के साथ रिकर्सन)

प्रत्येक नोड के लिए दो विकल्प:

  • शामिल करें: नोड का मान + पोते-पोतियों का अधिकतम योग।
  • बाहर करें: बाएं और दाएं बच्चे के अधिकतम योग का योग।

मैप mp में परिणाम कैश करें।

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

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

struct node {
    int data;
    struct node *left, *right;
};

struct node* newNode(int data) {
    struct node *temp = new struct node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int sumOfGrandChildren(node* node, map& mp);
int getMaxSumUtil(node* node, map& mp);

int sumOfGrandChildren(node* node, map& mp) {
    int sum = 0;
    if (node->left)
        sum += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp);
    if (node->right)
        sum += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp);
    return sum;
}

int getMaxSumUtil(node* node, map& mp) {
    if (node == NULL) return 0;
    if (mp.find(node) != mp.end()) return mp[node];
    int incl = node->data + sumOfGrandChildren(node, mp);
    int excl = getMaxSumUtil(node->left, mp) + getMaxSumUtil(node->right, mp);
    mp[node] = max(incl, excl);
    return mp[node];
}

int getMaxSum(node* node) {
    if (node == NULL) return 0;
    map mp;
    return getMaxSumUtil(node, mp);
}

int main() {
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(4);
    root->right->right = newNode(5);
    root->left->left = newNode(1);
    cout << getMaxSum(root) << endl;
    return 0;
}

आउटपुट

11
  1. सर्कुलर ऐरे में अधिकतम योग जहाँ कोई दो आसन्न तत्व न हों - C++ सर्कुलर ऐरे में अधिकतम योग जहाँ कोई दो आसन्न तत्व न हों - C++

    इस समस्या में, हमें एक सर्कुलर ऐरे cirArr[] दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में सर्कुलर ऐरे में अधिकतम योग ढूंढे जहाँ कोई दो आसन्न तत्व न हों।समस्या विवरणसर्कुलर ऐरे के लिए, हमें ऐरे के तत्वों का अधिकतम योग ढूंढना है जहाँ आसन्न तत्वों को नहीं लिया जा सकता, यानी हमें वैकल्पिक तत

  1. C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम ढूंढेगा।बाइनरी ट्री का स्पाइरल सम  बाइनरी ट्री के स्पाइरल ट्रैवर्सल में मिलने वाले नोड्स का योग है।ट्री के स्पाइरल ट्रैवर्सल में, नोड्स को रूट से लीफ नोड तक ट्रैवर्स कि

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

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज