ধরুন আমাদের একটি বাইনারি গাছ আছে। গাছটি সম্পূর্ণ বাইনারি ট্রি কি না তা দেখতে হবে। লেভেল n-এর একটি সম্পূর্ণ বাইনারি ট্রি, যার n-1 সম্পূর্ণ স্তর রয়েছে এবং n স্তরের সমস্ত নোড বাম দিক থেকে পূর্ণ। তাই যদি ইনপুট ট্রি −
এর মত হয়
তাহলে আউটপুট সত্য হবে, যেহেতু এটি সম্পূর্ণ বাইনারি ট্রি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
যদি গাছ খালি থাকে, তাহলে শূন্য ফেরত দিন
-
একটি সারি q তৈরি করুন এবং এতে রুট প্রবেশ করান
-
পতাকা সেট করুন :=সত্য
-
যখন q এর কিছু উপাদান আছে
-
sz :=সারির আকার
-
যখন sz 0
নয়-
নোড :=সারি থেকে মুছে ফেলার পরে নোড
-
যদি নোড সাবট্রি ছেড়ে থাকে, তাহলে
-
যদি পতাকা সেট করা থাকে, তাহলে q-তে নোডের বাম সাবট্রি ঢোকান, অন্যথায় মিথ্যা রিটার্ন করুন
-
-
অন্যথায় পতাকা :=মিথ্যা
-
যদি নোডের ডান সাবট্রি থাকে, তাহলে
-
যদি পতাকা সেট করা থাকে, তাহলে q-তে নোডের ডান সাবট্রি সন্নিবেশ করুন, অন্যথায় মিথ্যা ফেরত দিন
-
-
পতাকা :=মিথ্যা
-
sz :=sz – 1
-
-
-
রিটার্ন টাউর
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
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:
bool isCompleteTree(TreeNode* root) {
if(!root)return true;
queue <TreeNode*> q;
q.push(root);
bool isComplete = true;
while(!q.empty()){
int sz = q.size();
while(sz--){
TreeNode* node = q.front();
q.pop();
if(node->left){
if(isComplete){
q.push(node->left);
}else return false;
}else{
isComplete = false;
}
if(node->right){
if(isComplete){
q.push(node->right);
}else return false;
}else{
isComplete = false;
}
}
}
return true;
}
};
main(){
vector<int> v = {1,2,3,4,5,6};
TreeNode *r1 = make_tree(v);
Solution ob;
cout << (ob.isCompleteTree(r1));
} ইনপুট
{1,2,3,4,5,6} আউটপুট
1
