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

C++ में जांचें कि बाइनरी ट्री ऊंचाई-संतुलित है या नहीं


एक बाइनरी ट्री ऊंचाई-संतुलित (height-balanced) होता है यदि प्रत्येक नोड के लिए उसके बाएं और दाएं सबट्री की ऊंचाई का निरपेक्ष अंतर 0 या 1 हो।

दिए गए ट्री के लिए आउटपुट true (1) है।

समाधान दृष्टिकोण (पोस्ट-ऑर्डर DFS)

  1. एक ग्लोबल फ्लैग ret = true रखें।
  2. dfs(node) फंक्शन नोड की ऊंचाई वापस करता है:
    • यदि नोड नल, तो 0 वापस करें।
    • बाएं और दाएं सबट्री की ऊंचाई पाएं: l = 1 + dfs(left), r = 1 + dfs(right)।
    • यदि |l - r| > 1, तो ret = false सेट करें।
    • max(l, r) वापस करें।
  3. मुख्य फंक्शन dfs(root) कॉल करता है और ret वापस करता है।

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

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool ret;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int l = 1 + dfs(node->left);
        int r = 1 + dfs(node->right);
        if (abs(l - r) > 1) ret = false;
        return max(l, r);
    }
    bool isBalanced(TreeNode* root) {
        ret = true;
        dfs(root);
        return ret;
    }
};

int main() {
    Solution ob;
    TreeNode *root = new TreeNode(25);
    root->left = new TreeNode(19);
    root->right = new TreeNode(4);
    root->left->left = new TreeNode(9);
    root->left->right = new TreeNode(7);
    cout << ob.isBalanced(root);
    return 0;
}

इनपुट

TreeNode *root = new TreeNode(25); root->left = new TreeNode(19); root->right = new TreeNode(4); root->left->left = new TreeNode(9); root->left->right = new TreeNode(7);

आउटपुट

1
  1. दिए गए बाइनरी ट्री की प्रूनिंग करने का प्रोग्राम C++ में दिए गए बाइनरी ट्री की प्रूनिंग करने का प्रोग्राम C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है, जहां प्रत्येक नोड का मान या तो 0 या 1 है। हमें वही ट्री ढूंढना है जहां 1 न रखने वाले हर उपट्री को हटा दिया गया हो। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे - एक रिकर्सिव विधि solve() परिभाषित करें, यह नोड लेगी। विधि इस तरह होगी - यदि नोड null है, तो null

  1. C++ में जांचें कि दिया गया ट्री ग्राफ रैखिक है या नहीं C++ में जांचें कि दिया गया ट्री ग्राफ रैखिक है या नहीं

    यहां हम देखेंगे कि ट्री ग्राफ रैखिक है या नहीं, इसकी जांच कैसे करें। एक रैखिक ट्री ग्राफ को एक ही पंक्ति में व्यक्त किया जा सकता है। मान लीजिए यह एक रैखिक ट्री ग्राफ का उदाहरण है।लेकिन यह रैखिक नहीं है -किसी ग्राफ की जांच करने के लिए कि वह रैखिक है या नहीं, हम दो शर्तों का पालन कर सकते हैं:यदि नोड्स

  1. C++ प्रोग्राम: जांचें कि क्या एक ग्राफ दृढ़ता से जुड़ा हुआ है या नहीं C++ प्रोग्राम: जांचें कि क्या एक ग्राफ दृढ़ता से जुड़ा हुआ है या नहीं

    निर्देशित ग्राफ में घटकों को दृढ़ता से जुड़ा हुआ कहा जाता है, जब एक घटक में वर्टेक्स के प्रत्येक जोड़े के बीच एक पथ होता है। इस एल्गोरिदम को हल करने के लिए, पहले, प्रत्येक वर्टेक्स का फिनिश टाइम प्राप्त करने के लिए DFS एल्गोरिदम का उपयोग किया जाता है, अब ट्रांसपोज़्ड ग्राफ का फिनिश टाइम ढूंढें, फि