C++ में अद्वितीय बाइनरी सर्च ट्री II

समस्या

मान लीजिए हमारे पास एक पूर्णांक n है, हमें उन सभी संरचनात्मक रूप से अद्वितीय बाइनरी सर्च ट्री को उत्पन्न करना है जो 1 से n तक के मान संग्रहीत करते हैं। उदाहरण के लिए, यदि इनपुट 3 है, तो ट्री इस प्रकार होंगे:

समाधान दृष्टिकोण

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

generate() नामक एक पुनरावर्ती फ़ंक्शन परिभाषित करें, यह low और high लेगा
temp नामक एक ट्री नोड परिभाषित करें।
यदि low > high, तो temp में null डालें, और temp लौटाएं
i को low से high तक लूप में
- left_subtree := generate(low, i - 1)
- right_subtree := generate(i + 1, high)
- current := i
- j को 0 से left_subtree के आकार तक लूप में
  - k को 0 से right_subtree के आकार तक लूप में
    - curr_node := current मान के साथ एक ट्री नोड बनाएं
    - curr_node का बायाँ := left_subtree[j]
    - curr_node का दायाँ := right_subtree[k]
    - curr_node को temp में डालें
temp लौटाएं।
प्रारंभ में 1 और n मानों के साथ generate() फ़ंक्शन को कॉल करके सभी ट्री उत्पन्न करें।

उदाहरण (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, ]