ধরুন আমাদের কাছে ডট (.) এবং একটি সংখ্যা সহ একটি স্ট্রিং আছে, একটি বিন্দু নির্দেশ করে যে ঘরটি খালি আছে এবং যদি কোনো ঘরে একটি সংখ্যা x থাকে তবে এটি নির্দেশ করে যে আমরা স্ট্রিংয়ের মধ্যে x ধাপ ডানে বা বামে যেতে পারি। আমাদের কাজ হল আমরা একাধিকবার একটি সেল পরিদর্শন করতে পারি কিনা তা পরীক্ষা করা। উদাহরণস্বরূপ, যদি একটি স্ট্রিং "এর মতো হয়। 2 . . 2 .", তাহলে আমরা দুটি ভিন্ন উপায়ে 4র্থ কক্ষ পরিদর্শন করতে পারি। দ্বিতীয় ঘর থেকে দুই ধাপ ডানে, অথবা ঘর 6 থেকে দুই ধাপ বাম।
স্ট্রিং এর ith সেলটি কতবার পরিদর্শন করা যেতে পারে তার ট্র্যাক রাখতে আমরা ভিজিটেড[] নামে একটি অ্যারে ব্যবহার করব। এখন স্ট্রিংটি অতিক্রম করুন এবং বর্তমান অক্ষরটি ডট বা একটি সংখ্যা কিনা তা পরীক্ষা করুন। বিন্দুর জন্য, x-এর জন্য কিছুই করবেন না, সংখ্যা বাড়ান এবং পরিদর্শন করা অ্যারেতে [i – x, i + x] পরিসরের ভিজিট সংখ্যা 1 দ্বারা বৃদ্ধি করুন। পরিদর্শন করা অ্যারে অতিক্রম করে, যদি আমরা কিছু রুম পাই তাহলে পরিদর্শন করা হবে। একাধিকবার বা না।
উদাহরণ
#include <iostream>
#include <queue>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node* getNode(int key) {
Node* newNode = new Node;
newNode->key = key;
newNode->left = newNode->right = NULL;
return newNode;
}
bool isLevelWiseSorted(Node* root) {
int prevMax = INT_MIN;
int min_val, max_val;
int levelSize;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
levelSize = q.size();
min_val = INT_MAX;
max_val = INT_MIN;
while (levelSize > 0) {
root = q.front();
q.pop();
levelSize--;
min_val = min(min_val, root->key);
max_val = max(max_val, root->key);
if (root->left)
q.push(root->left);
if (root->right)
q.push(root->right);
}
if (min_val <= prevMax)
return false;
prevMax = max_val;
}
return true;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
if (isLevelWiseSorted(root))
cout << "Tree is levelwise Sorted";
else
cout << "Tree is Not levelwise sorted";
} আউটপুট
Tree is level wise Sorted
