C++ এ অনন্য বাইনারি অনুসন্ধান ট্রি II

ধরুন আমাদের একটি পূর্ণসংখ্যা n আছে, আমাদেরকে 1 থেকে n পর্যন্ত মান সংরক্ষণ করে এমন সমস্ত কাঠামোগতভাবে অনন্য বাইনারি অনুসন্ধান ট্রি তৈরি করতে হবে। সুতরাং যদি ইনপুট 3 হয়, তাহলে গাছগুলি হবে −

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

generate() নামক একটি পুনরাবৃত্ত ফাংশন সংজ্ঞায়িত করুন, এটি কম এবং বেশি লাগবে
টেম্প নামে একটি ট্রি নোড সংজ্ঞায়িত করুন।
যদি কম> উচ্চ হয়, তাহলে টেম্পে নাল ঢোকান এবং টেম্প রিটার্ন করুন
আমার জন্য নিম্ন থেকে উচ্চ পরিসরে
- left_subtree :=generate(low, i – 1)
- right_subtree :=generate(i + 1, high)
- কারেন্ট :=i
- j-এর জন্য রেঞ্জ 0 থেকে বাম_সাবট্রির মাপ
  - k এর জন্য রেঞ্জ 0 থেকে ডান_সাবট্রির মাপ
    - curr_node :=মান কারেন্ট সহ একটি ট্রি নোড তৈরি করুন
    - curr_node এর বাম :=left_subtree[j]
    - curr_node এর ডানে :=right_subtree[k]
    - টেম্পে curr_node ঢোকান
রিটার্ন টেম্প।
প্রাথমিকভাবে generate() ফাংশনটিকে 1 এবং n মান সহ সমস্ত ট্রি তৈরি করতে কল করুন।

উদাহরণ(C++)

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

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = 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;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
      cout << "[";
   queue<TreeNode *> q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      }
      else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr == NULL || curr->val == 0){
            cout << "null" << ", ";
         }
         else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<TreeNode*> generate(int low, int high) {
      vector <TreeNode*> temp;
      if(low > high){
         temp.push_back(NULL);
         return temp;
      }
      for(int i = low;i<=high;i++){
         vector <TreeNode*> leftSubtree = generate(low,i-1);
         vector <TreeNode*> rightSubtree = generate(i+1,high);
         int current = i;
         for(int j = 0;j<leftSubtree.size();j++){
            for(int k =0;k<rightSubtree.size();k++){
               TreeNode* currentNode = new TreeNode(current);
               currentNode->left = leftSubtree[j];
               currentNode->right = rightSubtree[k];
               temp.push_back(currentNode);
            }
         }
      }
      return temp;
   }
   vector<TreeNode*> generateTrees(int n) {
      if(!n){
         vector <TreeNode*> r;
         return r;
      }
      return generate(1,n) ;
   }
};
main(){
   Solution ob;
   vector<TreeNode*> v = ob.generateTrees(3);
   for(int i = 0; i<v.size(); i++)
      tree_level_trav(v[i]);
}

ইনপুট

আউটপুট

[1, 2, 3, ]
[1, 3, 2, ]
[2, 1, 3, ]
[3, 1, 2, ]
[3, 2, 1, ]