ধরুন 0 থেকে n - 1 পর্যন্ত নম্বরযুক্ত nটি বাইনারি ট্রি নোড আছে, যেখানে নোড i-এর দুটি চাইল্ড leftChild[i] এবং rightChild[i]। আমাদের true রিটার্ন করতে হবে যদি এবং কেবল যদি সব দেওয়া নোডগুলো মিলে ঠিক একটি ভ্যালিড বাইনারি ট্রি তৈরি করে। যখন নোড i-র লেফট চাইল্ড নেই, তখন leftChild[i] = -1, ডান চাইল্ডের জন্যও একই। মনে রাখবেন নোডগুলোর কোনো ভ্যালু নেই, শুধু নোড নম্বর ব্যবহার করা হয়েছে। ইনপুট নিচের মতো হলে −
আউটপুট হবে true।
সমাধানের ধাপগুলো:
dfs মেথড ডিফাইন করুন, যা leftChild, rightChild, visited নেবে
যদি নোড n ভিজিটেড থাকে, তবে false রিটার্ন করুন
নোড n visited সেটে ইনসার্ট করুন
ret := true সেট করুন
যদি leftChild[n] != -1 হয়, তবে ret := ret AND dfs(leftChild[n], leftChild, rightChild, visited)
যদি rightChild[n] != -1 হয়, তবে ret := ret AND dfs(rightChild[n], leftChild, rightChild, visited)
ret রিটার্ন করুন
মেইন মেথড:
ret := dfs(0, leftChild, rightChild, visited)
allVisited := false সেট করুন
i = 0 থেকে n – 1 পর্যন্ত লুপ চালান
যদি i visited নয়, তবে false রিটার্ন করুন
ret রিটার্ন করুন
উদাহরণ (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
