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