ধরুন আমাদের 0 থেকে n - 1 পর্যন্ত সংখ্যাযুক্ত n বাইনারি ট্রি নোড রয়েছে যেখানে নোড I-এর দুটি সন্তান leftChild[i] এবং rightChild[i] আছে, আমাদের সত্য বলতে হবে যদি এবং শুধুমাত্র যদি সমস্ত প্রদত্ত নোড ঠিক একটি বৈধ বাইনারি গাছ গঠন করে। যখন নোড i কোন বাম সন্তান নেই তখন leftChild[i] সমান হবে -1, একইভাবে ডান সন্তানের জন্য। আমাদের মনে রাখতে হবে যে নোডের কোনো মান নেই এবং আমরা এই সমস্যায় শুধুমাত্র নোড নম্বর ব্যবহার করি। তাই যদি ইনপুট −
এর মত হয় 
তারপর আউটপুট সত্য হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
dfs নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি লেফটচাইল্ড, রাইটচাইল্ড এবং ভিজিট করা হবে
-
যদি নোড n পরিদর্শন করা হয়, তাহলে মিথ্যা ফেরত দিন
-
পরিদর্শন করা সেটে নোড এন প্রবেশ করান
-
সেট ret :=সত্য
-
যদি n-এর leftChild -1 না হয়, তাহলে ret :=ret AND dfs(leftChild[node], leftChild, rightChild, visited)
-
যদি n-এর rightChild -1 না হয়, তাহলে ret :=ret AND dfs(rightChild[node], leftChild, rightChild, visited)
-
রিটার্ন রিটার্ন
-
মূল পদ্ধতিটি হবে −
এর মত -
ret :=dfs(0, leftChild, rightChild, পরিদর্শন করা হয়েছে)
-
সেট allVisited :=মিথ্যা
-
আমি 0 থেকে n – 1
পরিসরে-
যদি আমাকে পরিদর্শন না করা হয়, তাহলে মিথ্যা ফেরত দিন
-
-
রিটার্ন রিটার্ন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool dfs(int node, vector <int>& leftChild, vector <int>& rightChild, set <int>& visited){
if(visited.count(node)) return false;
visited.insert(node);
bool ret = true;
if(leftChild[node] != -1){
ret &= dfs(leftChild[node], leftChild, rightChild, visited);
}
if(rightChild[node] != -1){
ret &= dfs(rightChild[node], leftChild, rightChild, visited);
}
return ret;
}
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
set <int> visited;
bool ret = dfs(0, leftChild, rightChild, visited);
bool allVisited = true;
for(int i = 0; i < n; i++){
if(!visited.count(i))return false;
}
return ret;
}
};
main(){
vector<int> v1 = {1,-1,3,-1}, v2 = {2,-1,-1,-1};
Solution ob;
cout << (ob.validateBinaryTreeNodes(4, v1, v2));
} ইনপুট
4 [1,-1,3,-1] [2,-1,-1,-1]
আউটপুট
1
