मान लीजिए हमारे पास एक बाइनरी ट्री है जहां रूट से किसी भी लीफ तक जाने वाला प्रत्येक पथ एक वैध अनुक्रम बनाता है, हमें जांचना है कि दी गई स्ट्रिंग ऐसी बाइनरी ट्री में एक वैध अनुक्रम है या नहीं।
हमें दी गई स्ट्रिंग पूर्णांकों की सरणी arr के संयोजन से मिलती है और एक पथ के साथ सभी नोड्स के मानों का संयोजन एक अनुक्रम बनाता है।
उदाहरण के लिए, यदि arr = [0,1,0,1], तो आउटपुट True होगा, क्योंकि पथ 0 -> 1 -> 0 -> 1 एक वैध अनुक्रम है (हरा रंग)। अन्य वैध अनुक्रम होंगे: 0 -> 1 -> 1 -> 0, 0 -> 0 -> 0।
हल करने की विधि
हम रिकर्सिव दृष्टिकोण का उपयोग करेंगे:
solve()फ़ंक्शन परिभाषित करें जो नोड, सरणी v, और इंडेक्स idx लेता है।- यदि नोड null है या idx सरणी आकार से बाहर है या नोड का मान v[idx] से मेल नहीं खाता, तो false लौटाएं।
- यदि नोड लीफ है, तो जांचें कि idx अंतिम इंडेक्स है या नहीं।
- बाएं और दाएं उपट्री के लिए रिकर्सिवली कॉल करें।
- मुख्य विधि से solve(root, arr) कॉल करें।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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
