सी ++ में बाइनरी ट्री नोड्स को मान्य करें

मान लीजिए कि हमारे पास n बाइनरी ट्री नोड्स हैं जिनकी संख्या 0 से n-1 तक है, जहां नोड I के दो बच्चे हैं। सभी दिए गए नोड्स बिल्कुल एक वैध बाइनरी ट्री बनाते हैं। जब नोड मेरे पास कोई बायां बच्चा नहीं है तो बाएं बच्चे [i] बराबर -1 होगा, इसी तरह दाएं बच्चे के लिए। हमें यह ध्यान रखना होगा कि नोड्स का कोई मूल्य नहीं है और हम इस समस्या में केवल नोड नंबरों का उपयोग करते हैं। तो अगर इनपुट की तरह है -

तब आउटपुट सही होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• डीएफएस नामक एक विधि को परिभाषित करें, यह लेफ्टचाइल्ड, राइटचाइल्ड और विजिट की जाएगी

• यदि नोड n का दौरा किया जाता है, तो झूठी वापसी करें

• विज़िट किए गए सेट में नोड n डालें

• रिट सेट करें:=सच

• यदि n का बायां बच्चा -1 नहीं है, तो ret :=ret AND dfs(leftChild[node], leftChild, rightChild, विज़िट किया गया)

• यदि n का दायाँ बच्चा -1 नहीं है, तो ret :=ret और dfs(rightChild[node], leftChild, rightChild, विज़िट किया गया)

• वापसी रिट

• मुख्य विधि इस प्रकार होगी -

• ret :=dfs(0, leftChild, rightChild, विज़िट किया गया)

• सभी विज़िट किए गए सेट करें:=असत्य

• I के लिए 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