C++ में फ्लिप-समतुल्य बाइनरी ट्री

मान लीजिए हमारे पास दो बाइनरी ट्री हैं। एक फ्लिप ऑपरेशन में किसी नोड के बाएँ और दाएँ सबट्री को स्वैप करना शामिल है। ट्री X, ट्री Y के फ्लिप-समतुल्य (flip equivalent) है यदि हम X में कुछ फ्लिप ऑपरेशन्स करके Y प्राप्त कर सकते हैं। हमें निर्धारित करना है कि दो दिए गए बाइनरी ट्री (रूट root1 और root2) फ्लिप-समतुल्य हैं या नहीं।

उदाहरण: यदि हम मान 1, 3 और 5 वाले नोड्स को फ्लिप करें, तो ट्री समतुल्य हो जाते हैं, इसलिए आउटपुट true होगा।

रिकर्सिव एल्गोरिदम

1. solve(t1, t2) रिकर्सिव फंक्शन परिभाषित करें।
2. यदि दोनों null हैं, तो true लौटाएँ।
3. यदि एक null है और दूसरा नहीं, तो false लौटाएँ।
4. यदि t1->val != t2->val, तो false लौटाएँ।
5. यदि (दोनों के बाएँ सबट्री null हैं) OR (दोनों के बाएँ सबट्री मौजूद हैं और उनके मान समान हैं):
   • return solve(t1->left, t2->left) && solve(t1->right, t2->right) लौटाएँ।
6. अन्यथा:
   • return solve(t1->left, t2->right) && solve(t1->right, t2->left) लौटाएँ (फ्लिप मानकर)।

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 flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return true;
        if (!root1 || !root2) return false;
        if (root1->val != root2->val) return false;
        
        bool leftMatch = (!root1->left && !root2->left) || 
                         (root1->left && root2->left && root1->left->val == root2->left->val);
        
        if (leftMatch) {
            return flipEquiv(root1->left, root2->left) && 
                   flipEquiv(root1->right, root2->right);
        } else {
            return flipEquiv(root1->left, root2->right) && 
                   flipEquiv(root1->right, root2->left);
        }
    }
};

int main() {
    // ट्री बनाने का कोड यहाँ होगा
    Solution ob;
    // cout << ob.flipEquiv(r1, r2);
    return 0;
}

इनपुट

[1,2,3,4,5,6,null,null,null,7,8] [1,3,2,null,6,4,5,null,null,null,null,8,7]

आउटपुट

1