मान लीजिए हमारे पास 0 से n-1 तक नंबरेड n बाइनरी ट्री नोड्स हैं जहां नोड i के दो चिल्ड्रन leftChild[i] और rightChild[i] हैं, हमें true कहना है यदि और केवल यदि सभी दिए गए नोड्स ठीक एक वैलिड बाइनरी ट्री बनाते हैं। जब नोड i का कोई लेफ्ट चाइल्ड नहीं होता तो leftChild[i] -1 के बराबर होगा, इसी तरह राइट चाइल्ड के लिए। हमें ध्यान रखना होगा कि नोड्स की कोई वैल्यू नहीं है और हम इस समस्या में केवल नोड नंबर्स का उपयोग करते हैं। उदाहरण के लिए, अगर इनपुट है:
तो आउटपुट true होगा।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
dfs नाम का एक मेथड डिफाइन करें, जो leftChild, rightChild और visited लेगा
अगर नोड n विजिटेड है, तो false लौटाएं
नोड n को विजिटेड सेट में इंसर्ट करें
ret := true सेट करें
अगर 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 लौटाएं
मेन मेथड इस तरह होगा:
ret := dfs(0, leftChild, rightChild, visited)
allVisited := false सेट करें
i को 0 से n-1 तक लूप करें:
अगर i विजिटेड नहीं है, तो 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;
}
};
int 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
