C++ में सभी संभावित फुल बाइनरी ट्रीज़

मान लीजिए एक फुल बाइनरी ट्री एक बाइनरी ट्री है जहां प्रत्येक नोड के ठीक 0 या 2 बच्चे होते हैं। इसलिए हमें N नोड्स वाले सभी संभावित फुल बाइनरी ट्रीज़ की सूची ढूंढनी है। उत्तर में प्रत्येक ट्री के प्रत्येक नोड का node.val = 0 होना चाहिए। लौटाए गए ट्री किसी भी क्रम में हो सकते हैं। यदि इनपुट 7 है, तो ट्री हैं -

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -

• इंटीजर टाइप की और ट्री टाइप वैल्यू के मैप m को परिभाषित करें।
• allPossibleFBT() नामक एक मेथड परिभाषित करें, यह N को इनपुट के रूप में लेगा
• यदि N 1 है, तो 0 मान वाले एक नोड के साथ एक ट्री बनाएं, और लौटाएं
• यदि m में की N है, तो m[N] लौटाएं। एक ऐरे टेम्प परिभाषित करें, और req := N - 1
• लेफ्ट के लिए 1 से req - 1 तक की रेंज में
  • राइट := req - लेफ्ट
  • यदि लेफ्ट = 2 या राइट = 2 है, तो अगले इटरेशन के लिए जाएं
  • लेफ्टपार्ट := allPossibleFBT(लेफ्ट), राइटपार्ट := allPossibleFBT(राइट)
  • j के लिए 0 से लेफ्टपार्ट के आकार - 1 तक की रेंज में
    • k के लिए 0 से राइटपार्ट के आकार - 1 तक की रेंज में
      • रूट := 0 मान के साथ एक नया नोड
      • रूट का लेफ्ट := लेफ्टपार्ट[j], रूट का राइट := राइटपार्ट[k]
      • रूट को ans में डालें
• m[N] := ans सेट करें और लौटाएं।

उदाहरण (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 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:    map < int, vector <TreeNode*> > m;    vector<TreeNode*> allPossibleFBT(int N) {       if(N == 1){          vector <TreeNode*> temp;          TreeNode *n = new TreeNode(1);          n->left = new TreeNode(0);          n->right = new TreeNode(0);          temp.push_back(n);          return temp;       }       if(m.count(N))return m[N];       vector <TreeNode*> ans;       int required = N - 1;       for(int left = 1; left < required; left++){          int right = required - left;          if(left == 2 || right == 2)continue;          vector <TreeNode*> leftPart = allPossibleFBT(left);          vector <TreeNode*> rightPart = allPossibleFBT(right);          for(int j = 0; j < leftPart.size(); j++){             for(int k = 0; k < rightPart.size(); k++){                TreeNode* root = new TreeNode(1);                root->left = leftPart[j];                root->right = rightPart[k];                ans.push_back(root);             }          }       }       return m[N] = ans;    } }; main(){    vector<TreeNode*> v;    Solution ob;    v = (ob.allPossibleFBT(7)) ;    for(TreeNode *t : v){       tree_level_trav(t);    } }

इनपुट

7

आउटपुट

[1, 1, 1, null, null, 1, 1, null, null, 1, 1, null, null, null, null, ] [1, 1, 1, null, null, 1, 1, 1, 1, null, null, null, null, null, null, ] [1, 1, 1, 1, 1, 1, 1, null, null, null, null, null, null, null, null, ] [1, 1, 1, 1, 1, null, null, null, null, 1, 1, null, null, null, null, ] [1, 1, 1, 1, 1, null, null, 1, 1, null, null, null, null, null, null, ]