C++ में बाइनरी ट्री में कजिन्स (चचेरे भाई)

मान लीजिए हमारे पास एक बाइनरी ट्री है, जहां रूट नोड गहराई 0 पर है, और प्रत्येक गहराई k के नोड के बच्चे गहराई k+1 पर होते हैं।

बाइनरी ट्री के दो नोड्स को कजिन्स (चचेरे भाई) कहा जाता है यदि वे समान गहराई पर हैं, लेकिन उनके माता-पिता अलग-अलग हैं।

ट्री के सभी मान अद्वितीय होंगे, और दो अलग-अलग नोड्स के मान x और y दिए गए हैं। हमें जांचना है कि x और y मान वाले नोड्स कजिन्स हैं या नहीं।

उदाहरण के लिए, यदि इनपुट ट्री में x = 5, y = 4 है, तो आउटपुट true होगा।

समाधान दृष्टिकोण

एक अनऑर्डर्ड मैप um परिभाषित करें जो नोड मान को उसके पैरेंट नोड से मैप करेगा।
एक कतार q परिभाषित करें और रूट को इसमें डालें।
um[x] = um[y] = NULL सेट करें।
जब तक कतार खाली नहीं है:
- वर्तमान लेवल का आकार qSize लें।
- इस लेवल के सभी नोड्स को प्रोसेस करें:
  - कतार से नोड cur निकालें।
  - यदि लेफ्ट चाइल्ड मौजूद है और उसका मान x या y है, तो um[मान] = cur सेट करें, अन्यथा कतार में डालें।
  - इसी तरह राइट चाइल्ड के लिए करें।
- लेवल प्रोसेस करने के बाद, यदि um[x] या um[y] में से कोई नॉन-NULL है:
  - यदि दोनों में से एक NULL है या दोनों समान पैरेंट की ओर इशारा करते हैं, तो false वापस करें।
  - अन्यथा true वापस करें।
false वापस करें।

उदाहरण (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 isCousins(TreeNode* root, int x, int y) { 
        unordered_map<int, TreeNode*> um; 
        queue<TreeNode*> q; 
        q.push(root); 
        um[x] = um[y] = NULL; 
        while (!q.empty()) { 
            int qSize = q.size(); 
            while (qSize-- > 0) { 
                auto cur = q.front(); 
                q.pop(); 
                if (cur->left) { 
                    if (um.count(cur->left->val)) 
                        um[cur->left->val] = cur; 
                    else 
                        q.push(cur->left); 
                } 
                if (cur->right) { 
                    if (um.count(cur->right->val)) 
                        um[cur->right->val] = cur; 
                    else 
                        q.push(cur->right); 
                } 
            } 
            if (um[x] || um[y]) { 
                if (!um[x] || !um[y] || um[x] == um[y]) 
                    return false; 
                else 
                    return true; 
            } 
        } 
        return false; 
    } 
}; 

int main() { 
    Solution ob; 
    TreeNode* root = new TreeNode(1); 
    root->left = new TreeNode(2); 
    root->right = new TreeNode(3); 
    root->left->right = new TreeNode(4); 
    root->right->right = new TreeNode(5); 
    cout << (ob.isCousins(root, 5, 4)); 
    return 0; 
}

इनपुट

TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(4); root->right->right = new TreeNode(5); cout << (ob.isCousins(root, 5, 4));