ধরুন আমাদের একটি বাইনারি ট্রি আছে যেখানে মূল থেকে যেকোনো পাতার দিকে যাওয়ার প্রতিটি পথ একটি বৈধ ক্রম তৈরি করে, আমাদের পরীক্ষা করতে হবে যে প্রদত্ত স্ট্রিংটি এই ধরনের বাইনারি ট্রিতে একটি বৈধ ক্রম কিনা।
আমরা প্রদত্ত স্ট্রিংটি পূর্ণসংখ্যার অ্যারের একটি অ্যারের সংযোজন থেকে পাব এবং একটি পথ বরাবর নোডের সমস্ত মানের সংযোজন একটি অনুক্রমের ফলে
ধরুন আমাদের একটি বাইনারি গাছ আছে।
সুতরাং, যদি arr =[0,1,0,1] হয়, তাহলে আউটপুটটি True হবে, কারণ পথ 0 -> 1 -> 0 -> 1 একটি বৈধ ক্রম (সবুজ রঙ)। অন্যান্য বৈধ ক্রম হবে :0 -> 1 -> 1 -> 0 , 0 -> 0 -> 0
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি নোড নেবে, একটি অ্যারে v, idx 0 দিয়ে শুরু করবে,
-
যদি নোড নাল হয়, তাহলে −
-
মিথ্যা ফেরত দিন
-
-
যদি idx>=v এর আকার হয়, তাহলে −
-
মিথ্যা ফেরত দিন
-
-
যদি নোডের ভ্যাল v[idx] এর সমান না হয়, তাহলে −
-
মিথ্যা ফেরত দিন
-
-
যদি নোডের কোনো সন্তান না থাকে, তাহলে -
-
idx ==আকারের v
হলে true রিটার্ন করুন
-
-
রিটার্ন সলভ (নোডের বামে, v, idx + 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;
}
};
class Solution {
public:
bool solve(TreeNode* node, vector <int>& v, int idx = 0){
if(!node) return false;
if(idx >= v.size()) return false;
if(node->val != v[idx]) return false;
if(!node->left && !node->right){
return idx == v.size() - 1;
}
return solve(node->left, v, idx + 1) || solve(node->right, v, idx + 1);
}
bool isValidSequence(TreeNode* root, vector<int>& arr) {
return solve(root, arr);
}
};
main(){
TreeNode *root = new TreeNode(0);
root->left = new TreeNode(1); root->right = new TreeNode(0);
root->left->left = new TreeNode(0); root->left->right = new
TreeNode(1);
root->right->left = new TreeNode(0);
root->left->left->right = new TreeNode(1);
root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);
Solution ob;
vector<int> v = {0,1,0,1};
cout << (ob.isValidSequence(root, v));
} ইনপুট
TreeNode *root = new TreeNode(0); root->left = new TreeNode(1); root->right = new TreeNode(0); root->left->left = new TreeNode(0); root->left->right = new TreeNode(1); root->right->left = new TreeNode(0); root->left->left->right = new TreeNode(1); root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);
আউটপুট
1
