जांचें कि क्या एक स्ट्रिंग सी ++ में एक बाइनरी ट्री में रूट से लीव्स पाथ तक एक वैध अनुक्रम है

मान लीजिए कि हमारे पास एक बाइनरी ट्री है जहां रूट से किसी भी पत्ते तक जाने वाला प्रत्येक पथ एक वैध अनुक्रम बनाता है, हमें यह जांचना होगा कि दिए गए स्ट्रिंग ऐसे बाइनरी ट्री में एक वैध अनुक्रम है या नहीं।

हम दिए गए स्ट्रिंग को पूर्णांकों की एक सरणी के संयोजन से प्राप्त करेंगे और एक पथ के साथ नोड्स के सभी मानों के संयोजन से अनुक्रम में परिणाम प्राप्त होंगे

मान लीजिए हमारे पास एक बाइनरी ट्री जैसा है।

इसलिए, यदि arr =[0,1,0,1] है, तो आउटपुट सही होगा, क्योंकि पथ 0 -> 1 -> 0 -> 1 एक वैध अनुक्रम (हरा रंग) है। अन्य मान्य क्रम होंगे:0 -> 1 -> 1 -> 0, 0 -> 0 -> 0

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

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह नोड लेगा, एक सरणी v, idx इसे 0 से प्रारंभ करें,

• यदि नोड शून्य है, तो -

  • झूठी वापसी

• अगर idx>=v का आकार, तो −

  • झूठी वापसी

• यदि नोड का मान v[idx] के बराबर नहीं है, तो -

  • झूठी वापसी

• यदि नोड की कोई संतान नहीं है, तो -

  • सही लौटें जब idx ==v का आकार

• रिटर्न सॉल्व (नोड के बाएँ, 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