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

C++ में बाइनरी ट्री में सिक्कों का वितरण


मान लीजिए हमारे पास N नोड्स वाला एक बाइनरी ट्री का रूट है, जहाँ प्रत्येक नोड में node.val संख्या में सिक्के हैं, और कुल N सिक्के हैं। एक चाल में, हम दो आसन्न नोड्स चुन सकते हैं और एक सिक्के को एक नोड से दूसरे नोड में ले जा सकते हैं (चाल पैरेंट से चाइल्ड या चाइल्ड से पैरेंट हो सकती है)। हमें वह चालों की संख्या ढूंढनी है जिससे हर नोड में ठीक एक सिक्का हो जाए।

उदाहरण: ट्री [0,3,0] (रूट=0, बायाँ=3, दायाँ=0) के लिए आउटपुट 3 होगा। बाएँ चाइल्ड से रूट में 2 सिक्के भेजें (2 चालें), फिर रूट से दाएँ चाइल्ड में 1 सिक्का भेजें (1 चाल)। कुल 3 चालें।

पोस्ट-ऑर्डर ट्रैवर्सल समाधान

  1. एक रिकर्सिव मेथड solve() परिभाषित करें जो एक नोड root लेता है।
  2. यदि root null है, तो 0 लौटाएँ।
  3. l := solve(root->left), r := solve(root->right)।
  4. ans += |l| + |r| (ग्लोबल उत्तर में निरपेक्ष मान जोड़ें)।
  5. return l + r + root->val - 1 लौटाएँ (यह नोड का अतिरिक्त/घाटा सिक्के दर्शाता है)।
  6. मुख्य फंक्शन में ans := 0 सेट करें, solve(root) कॉल करें, फिर ans लौटाएँ।

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; }
};

class Solution {
public:
    int ans = 0;
    int solve(TreeNode* root) {
        if (!root) return 0;
        int l = solve(root->left);
        int r = solve(root->right);
        ans += abs(l) + abs(r);
        return l + r + root->val - 1;
    }
    int distributeCoins(TreeNode* root) {
        ans = 0;
        solve(root);
        return ans;
    }
};

// ट्री बनाने के लिए हेल्पर फंक्शन (लेवल ऑर्डर इनपुट से)
TreeNode* make_tree(vector<int> v) {
    if (v.empty()) return NULL;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* curr = q.front(); q.pop();
        if (i < v.size() && v[i] != -1) {
            curr->left = new TreeNode(v[i]);
            q.push(curr->left);
        }
        i++;
        if (i < v.size() && v[i] != -1) {
            curr->right = new TreeNode(v[i]);
            q.push(curr->right);
        }
        i++;
    }
    return root;
}

int main() {
    vector<int> v = {0,3,0};
    TreeNode* root = make_tree(v);
    Solution ob;
    cout << ob.distributeCoins(root); // आउटपुट: 3
    return 0;
}

इनपुट

[0,3,0]

आउटपुट

3
  1. C++ में बाइनरी ट्री प्रूनिंग C++ में बाइनरी ट्री प्रूनिंग

    मान लीजिए हमारे पास एक बाइनरी ट्री का हेड नोड root है, जहाँ प्रत्येक नोड का मान या तो 0 या 1 है। हमें वही ट्री लौटाना है जहाँ हर वह सबट्री हटा दी गई हो जिसमें 1 नहीं है। उदाहरण: इनपुट ट्री [1,1,0,1,1,0,1,0] के लिए, आउटपुट ट्री में केवल वही नोड्स रहेंगे जिनके सबट्री में कम से कम एक 1 है। पोस्ट-ऑर्

  1. C++ में बाइनरी ट्री को लिंक्ड लिस्ट में फ्लैट करना C++ में बाइनरी ट्री को लिंक्ड लिस्ट में फ्लैट करना

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें इसे स्थानांतरित (in-place) करके लिंक्ड लिस्ट में बदलना है (दायाँ पॉइंटर अगले नोड को इंगित करे, बायाँ पॉइंटर null हो)। उदाहरण: ट्री [1,2,5,3,4] → फ्लैट लिस्ट: 1→2→3→4→5 (प्रीऑर्डर ट्रैवर्सल क्रम)। रिवर्स प्रीऑर्डर ट्रैवर्सल ग्लोबल prev = null रखें। रिकर

  1. C++ में बाइनरी ट्री का लेवल ऑर्डर ट्रैवर्सल (Binary Tree Level Order Traversal) C++ में बाइनरी ट्री का लेवल ऑर्डर ट्रैवर्सल (Binary Tree Level Order Traversal)

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें इस ट्री को लेवल ऑर्डर ट्रैवर्सल योजना का उपयोग करके पार करना है। यदि ट्री इस तरह है: ट्रैवर्सल अनुक्रम इस तरह होगा: [10, 5, 16, 8, 15, 20, 23] इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे: नोड्स संग्रहीत करने के लिए कतार que परिभाषित करें रूट क