মনে করুন একটি ফুল বাইনারি ট্রি হলো এমন একটি বাইনারি ট্রি যেখানে প্রতিটি নোডের ঠিক ০ অথবা ২টি চাইল্ড থাকে। তাহলে `N` নোড বিশিষ্ট সব সম্ভব ফুল বাইনারি ট্রির লিস্ট বের করতে হবে। প্রতিটি ট্রির প্রতিটি নোডের `node.val = 0` হতে হবে। রিটার্ন করা ট্রিগুলো যেকোনো অর্ডারে থাকতে পারে। যদি ইনপুট ৭ হয়, তবে ট্রিগুলো হবে -
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- ইন্টিজার টাইপ কি এবং ট্রি টাইপ ভ্যালু বিশিষ্ট একটি ম্যাপ `m` সংজ্ঞায়িত করুন।
- `allPossibleFBT()` নামক একটি মেথড সংজ্ঞায়িত করুন, এটি `N` ইনপুট নেবে
- যদি `N` ১ হয়, তবে ০ ভ্যালু দিয়ে এক নোডের ট্রি তৈরি করুন এবং রিটার্ন করুন
- যদি `m`-এ `N` কি থাকে, তবে `m[N]` রিটার্ন করুন • `ans` নামক একটি অ্যারে, এবং `req := N - 1` সংজ্ঞায়িত করুন
- `left` = 1 থেকে `req - 1` পর্যন্ত
- `right := req - left`
- যদি `left = 2` অথবা `right = 2`, তবে নেক্সট ইটারেশনে যান
- `leftPart := allPossibleFBT(left)`, `rightPart := allPossibleFBT(right)`
- `j` = 0 থেকে `leftPart`-এর আকার - 1 পর্যন্ত
- `k` = 0 থেকে `rightPart`-এর আকার - 1 পর্যন্ত
- `root :=` ০ ভ্যালু দিয়ে একটি নতুন নোড
- `root`-এর বাম := `leftPart[j]`, `root`-এর ডান := `rightPart[k]`
- `root`-কে `ans`-এ ইনসার্ট করুন
- `k` = 0 থেকে `rightPart`-এর আকার - 1 পর্যন্ত
- `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, ]
