C++ এ বাইনারি ট্রির সীমানা

ধরুন আমাদের একটি বাইনারি ট্রি আছে, আমাদের রুট থেকে শুরু করে ঘড়ির কাঁটার বিপরীত দিকে এর সীমানার মান খুঁজে বের করতে হবে। এখানে সীমানা ডুপ্লিকেট নোড ছাড়াই বাম সীমানা, পাতা এবং ডান সীমানা অন্তর্ভুক্ত করে।

• বাম সীমানা হল রুট থেকে বাম-সবচেয়ে নোডের পথ।

• ডান সীমানা হল রুট থেকে ডান-সবচেয়ে নোডের পথ।

• যখন মূলের বাম উপবৃক্ষ বা ডান উপবৃক্ষ থাকে না, তখন মূলটি নিজেই বাম সীমানা বা ডান সীমানা।

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

তাহলে আউটপুট হবে [1,2,4,7,8,9,10,6,3]

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

• একটি অ্যারে ret সংজ্ঞায়িত করুন

• একটি ফাংশন leftBoundary(), এটি নোড নেবে,

  সংজ্ঞায়িত করুন

• যদি নোড নাল হয় বা নোড পাতা হয়, তাহলে −

  • ফেরত

• ret

  -এ নোডের মান সন্নিবেশ করান

• যদি নোডের বাম অংশ থাকে, তাহলে -

  • leftBoundary(নোডের বাম)

• অন্যথায়

  • বাম সীমানা(নোডের ডানদিকে)

• একটি ফাংশন সংজ্ঞায়িত করুন rightBoundary(), এটি নোড নেবে,

• যদি নোড নাল হয় বা নোড পাতা হয়, তাহলে −

  • ফেরত

• ret

  -এ নোডের মান সন্নিবেশ করান

• যদি নোডের ডান উপস্থিত থাকে, তাহলে -

  • ডান বাউন্ডারি (নোডের বাম)

• অন্যথায়

  • rightBoundary(নোডের ডানদিকে)

• একটি ফাংশন পাতা (), এটি নোড নেবে,

  সংজ্ঞায়িত করুন

• যদি নোড উপস্থিত না থাকে, তাহলে -

  • ফেরত

• যদি নোড পাতা হয়, তাহলে −

  • ret এ নোডের ভ্যাল সন্নিবেশ করান

• পাতা (নোডের বাম)

• পাতা (নোডের ডানদিকে)

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• রেট অ্যারে সাফ করুন

• যদি root না থাকে, তাহলে −

  • রিটার্ন রিটার্ন

• ret এ রুটের ভ্যাল সন্নিবেশ করান

• বাম সীমানা(মূলের বাম)

• পাতা (মূলের বামে);

• পাতা (মূলের ডানদিকে);

• rightBoundary(মূলের ডানদিকে)

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
         right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   vector<int> ret;
   void leftBoundary(TreeNode* node){
      if (!node || node->val == 0 || (!node->left && !node->right))
         return;
      ret.push_back(node->val);
      if (node->left && node->left->val != 0)
         leftBoundary(node->left);
      else
         leftBoundary(node->right);
   }
   void rightBoundary(TreeNode* node){
      if (!node || node->val == 0 || (!node->left && !node->right))
         return;
      if (node->right && node->right->val != 0) {
         rightBoundary(node->right);
      }
      else {
         rightBoundary(node->left);
      }
      ret.push_back(node->val);
   }
   void leaves(TreeNode* node){
      if (!node || node->val == 0)
         return;
      if (!node->left && !node->right) {
         ret.push_back(node->val);
      }
      leaves(node->left);
      leaves(node->right);
   }
   vector<int> boundaryOfBinaryTree(TreeNode* root){
      ret.clear();
      if (!root)
         return ret;
      ret.push_back(root->val);
      leftBoundary(root->left);
      leaves(root->left);
      leaves(root->right);
      rightBoundary(root->right);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10};
   TreeNode *root = make_tree(v);
   print_vector(ob.boundaryOfBinaryTree(root));
}

ইনপুট

{1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10}

আউটপুট

[1, 2, 4, 7, 8, 9, 10, 6, 3, ]