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

C++ में उल्टे उपट्री (Inverted Subtree) की जांच


दो बाइनरी ट्री source और target दिए गए हैं। जांचें कि क्या source का कोई उल्टा रूप (inversion) target का उपट्री है। उल्टा रूप का अर्थ: बाएं और दाएं बच्चे वैकल्पिक रूप से स्वैप हो सकते हैं।

रिकर्सिव जांच: दो ट्री उल्टे हैं यदि (बाएं-बाएं और दाएं-दाएं मेल खाते हैं) या (बाएं-दाएं और दाएं-बाएं मेल खाते हैं)। target के प्रत्येक नोड पर यह जांच करें।

उदाहरण: दिए गए source और target के लिए आउटपुट true (1)।

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:
    bool check(TreeNode* node1, TreeNode* node2) {
        if (!node1 && !node2) return true;
        if (!node1 || !node2) return false;
        if (node1->val != node2->val) return false;
        bool op1 = check(node1->left, node2->left) && check(node1->right, node2->right);
        bool op2 = check(node1->right, node2->left) && check(node1->left, node2->right);
        return op1 || op2;
    }
    bool solve(TreeNode* source, TreeNode* target) {
        if (!target && !source) return true;
        if (!target || !source) return false;
        bool op1 = check(target, source);
        if (op1) return true;
        return solve(source, target->left) || solve(source, target->right);
    }
};

int main() {
    Solution ob;
    TreeNode* target = new TreeNode(6);
    target->left = new TreeNode(3);
    target->right = new TreeNode(1);
    target->right->left = new TreeNode(3);
    target->right->right = new TreeNode(2);
    target->right->right->left = new TreeNode(4);
    TreeNode* source = new TreeNode(1);
    source->left = new TreeNode(2);
    source->right = new TreeNode(3);
    source->left->right = new TreeNode(4);
    cout << ob.solve(source, target);
    return 0;
}

इनपुट

TreeNode *target = new TreeNode(6); target->left = new TreeNode(3); target->right = new TreeNode(1); target->right->left = new TreeNode(3); target->right->right = new TreeNode(2); target->right->right->left = new TreeNode(4); TreeNode *source = new TreeNode(1); source->left = new TreeNode(2); source->right = new TreeNode(3); source->left->right = new TreeNode(4);

आउटपुट

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

    मान लीजिए हमारे पास दो बाइनरी ट्री हैं और जब हम उनमें से एक को दूसरे पर रखते हैं, तो कुछ नोड्स ओवरलैप होते हैं जबकि अन्य नहीं। हमें उन्हें एक नए बाइनरी ट्री में मर्ज करना है। मर्ज नियम यह है कि यदि दो नोड्स ओवरलैप करते हैं, तो उनके मानों को जोड़कर मर्ज किए गए नोड का नया मान बनाया जाता है। अन्यथा, ग

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

    बाइनरी ट्री दिया गया है। उन नोड्स की गिनती करें जिनका मान उनके सभी वंशजों के मानों से बड़ा या बराबर हो। पोस्ट-ऑर्डर DFS: प्रत्येक नोड अपने सबट्री का अधिकतम मान वापस करता है। यदि नोड का मान ≥ max(बाएं_अधिकतम, दाएं_अधिकतम) तो गिनती बढ़ाएं। उदाहरण ट्री के लिए आउटपुट 4 (नोड 3 को छोड़कर सभी)। C++ कार्या

  1. C++ में जांचें कि बाइनरी ट्री किसी अन्य बाइनरी ट्री का सबट्री है या नहीं C++ में जांचें कि बाइनरी ट्री किसी अन्य बाइनरी ट्री का सबट्री है या नहीं

    मान लीजिए हमारे पास दो बाइनरी ट्री हैं। हमें जांचना है कि छोटा ट्री दूसरे बाइनरी ट्री का सबट्री है या नहीं। मान लीजिए ये दो ट्री दिए गए हैं।दो ट्री हैं। दूसरा ट्री पहले का सबट्री है। इस गुण की जांच करने के लिए, हम ट्री को पोस्ट-ऑर्डर फैशन में ट्रैवर्स करेंगे, फिर यदि इस नोड से रूटेड सबट्री दूसरे ट्र