C++ में बाइनरी ट्री में चचेरे भाई

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

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

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

तो, अगर इनपुट पसंद है

x =5, y =4, तो आउटपुट सही होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक नक्शा उम परिभाषित करें

• एक कतार को परिभाषित करें q

• q में रूट डालें

• उम [एक्स]:=उम [वाई]:=शून्य

• जबकि (नहीं q खाली है), करें -

  • qSize :=q का आकार

  • जबकि qSize> 0 तब (qSize को 1 से घटाएं), −

    . करें

    • cur :=q का पहला तत्व

    • q से तत्व हटाएं

    • यदि बाईं ओर कर्व मौजूद है, तो -

      • यदि उम में वक्र के बाईं ओर का मान है, तो

        • उम [कर के बाईं ओर का मान] :=वक्र

      • अन्यथा

        • क्यू में बाईं ओर डालें q

      • अगर उम में वक्र के अधिकार का मूल्य है, तो

        • उम [वक्र के अधिकार का मूल्य] :=वक्र

      • अन्यथा

        • क्यू में दायीं ओर डालें

    • अगर um[x] या um[y] गैर-शून्य है, तो -

      • यदि um[x] 0 है या um[y] 0 है या um[x] um[y] के समान है, तो -

        • झूठी वापसी

      • अन्यथा

        • सही लौटें

• झूठी वापसी

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#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 && cur->left->val != 0)
               if (um.count(cur->left->val))
                  um[cur->left->val] = cur;
               else
                  q.push(cur->left);
            if (cur->right && cur->right->val != 0)
               if (um.count(cur->right->val))
                  um[cur->right->val] = cur;
               else
                  q.push(cur->right);
         }
         if (um[x] or um[y])
            if (!um[x] or !um[y] or um[x] == um[y])
               return false;
            else
               return true;
      }
      return false;
   }
};
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));
}

इनपुट

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

आउटपुट

1