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

C++ में नोड और पूर्वज के बीच अधिकतम अंतर


मान लीजिए हमारे पास एक बाइनरी ट्री की रूट है, हमें अधिकतम मान V ढूंढना होगा जिसके लिए अलग-अलग नोड्स A और B मौजूद हैं जहां V = |A का मान - B का मान| और A, B का पूर्वज है।

इसलिए यदि ट्री इस तरह है:

C++ में नोड और पूर्वज के बीच अधिकतम अंतर


तो आउटपुट 7 होगा। पूर्वज नोड अंतर इस तरह हैं: [(8 - 3), (7 - 3), (8 - 1), (10-13)], उनमें से (8 - 1) = 7 अधिकतम है।

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

  • प्रारंभ में ans 0 परिभाषित करें

  • एक solve() विधि परिभाषित करें, यह ट्री नोड, currMin और currMax लेगा। यह इस तरह कार्य करेगा:

  • यदि नोड null है, तो लौटें

  • ans := ans का अधिकतम, |नोड का मान - currMin|, |नोड का मान - currMax|

  • solve(नोड का लेफ्ट, नोड के मान और currMin का न्यूनतम, नोड के मान और currMax का अधिकतम)

  • solve(नोड का राइट, नोड के मान और currMin का न्यूनतम, नोड के मान और currMax का अधिकतम)

  • मुख्य भाग में, solve(रूट, रूट का मान, रूट का मान) कॉल करें, और ans लौटाएं

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

उदाहरण

#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:
    int ans;
    void solve(TreeNode* node, int currMin, int currMax) {
        if (!node || node->val == 0) return;
        ans = max({ans, abs(node->val - currMin), abs(node->val - currMax)});
        solve(node->left, min(node->val, currMin), max(node->val, currMax));
        solve(node->right, min(node->val, currMin), max(node->val, currMax));
    }
    int maxAncestorDiff(TreeNode* root) {
        ans = 0;
        solve(root, root->val, root->val);
        return ans;
    }
};

int main() {
    vector<int> v = {8,3,10,1,6,NULL,14,NULL,NULL,4,7,13};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.maxAncestorDiff(root));
}

इनपुट

[8,3,10,1,6,null,14,null,null,4,7,13]

आउटपुट

7
  1. - C++ में new ऑपरेटर और operator new में क्या अंतर है?

    C++ में जब हम एक नया ऑब्जेक्ट बनाना चाहते हैं, तो हमें मेमोरी में एक मेमोरी ब्लॉक बनाना होगा, फिर उस मेमोरी ब्लॉक को आरंभ करने के लिए कंस्ट्रक्टर को भी कॉल करना होगा। हम new कीवर्ड का उपयोग करके मेमोरी एलिमेंट बना सकते हैं। यह new ऑपरेटर दो लगातार कार्य करता है। लेकिन operator new केवल मेमोरी स्पेस

  1. - C++ में 'struct' और 'typedef struct' में अंतर?

    C++ में, struct और typedef struct के बीच कोई अंतर नहीं है क्योंकि, C++ में, सभी struct/union/enum/class घोषणाएं ऐसा व्यवहार करती हैं जैसे वे इम्प्लिसिटली typedefed हैं, जब तक कि नाम उसी नाम की किसी अन्य घोषणा द्वारा छिपा नहीं जाता। हालांकि एक सूक्ष्म अंतर है कि typedefs को फॉरवर्ड डिक्लेयर नहीं किय

  1. - C++ स्ट्रिंग कॉन्स्टेंट्स और कैरेक्टर कॉन्स्टेंट्स में अंतर

    C++ में, सिंगल कोट्स में एक कैरेक्टर एक कैरेक्टर लिटरल है। इसका प्रकार char है। उदाहरण के लिए, a ASCII आधारित सिस्टम पर मान 97 के साथ char प्रकार का है। डबल कोट्स में एक कैरेक्टर या कैरेक्टर्स की स्ट्रिंग एक स्ट्रिंग लिटरल दर्शाती है। इसका प्रकार const char[] है और यह स्ट्रिंग की लंबाई + 1 के आकार