C++ এ বাইনারি ট্রিতে কাজিন

ধরুন আমাদের একটি বাইনারি গাছ আছে, রুট নোডটি গভীরতা 0 এ উপস্থিত রয়েছে এবং প্রতিটি k নোডের বাচ্চারা k+1 গভীরতায় রয়েছে।

এখানে একটি বাইনারি গাছের দুটি নোডকে কাজিন বলা হয় যদি তাদের গভীরতা একই থাকে তবে তাদের পিতামাতা আলাদা।

গাছের সমস্ত মান অনন্য হবে, এবং গাছের দুটি ভিন্ন নোডের x এবং y মান। x এবং y মানের সাথে সম্পর্কিত নোডগুলি কাজিন কিনা তা আমাদের পরীক্ষা করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

x =5, y =4, তাহলে আউটপুট সত্য হবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি মানচিত্র um
সংজ্ঞায়িত করুন
এক সারি q
সংজ্ঞায়িত করুন
q
-এ রুট সন্নিবেশ করান
um[x] :=um[y] :=শূন্য
যখন (q খালি নয়), −
করুন
- qSize :=q এর আকার
- যখন qSize> 0 তারপর (qSize 1 দ্বারা কমিয়ে দিন), −
  করুন
  - cur :=q এর প্রথম উপাদান
  - q
    থেকে উপাদান মুছুন
  - যদি curr এর বাম উপস্থিত থাকে, তাহলে −
    - যদি um-এর cur এর বাম দিকের মান থাকে, তাহলে
      - um[cur এর বাম দিকের মান] :=cur
    - অন্যথায়
      - q
        -এ cur-এর বাঁদিকে ঢোকান
    - যদি um এর cur এর অধিকারের মান থাকে, তাহলে
      - um[cur এর অধিকারের মান] :=cur
    - অন্যথায়
      - q
        -এ cur-এর ডানদিকে সন্নিবেশ করান
  - যদি 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));