मान लीजिए कि हमारे पास एक बाइनरी ट्री रूट है और पहले नोड के रूप में एक सिर के साथ एक लिंक्ड सूची है। हमें ट्रू वापस करना होगा यदि लिंक की गई सूची में सिर से शुरू होने वाले सभी तत्व बाइनरी ट्री में जुड़े कुछ डाउनवर्ड पथ से मेल खाते हैं अन्यथा गलत। तो अगर पेड़ जैसा है -
और लिंक की गई सूची [1,4,2,6] है, तो आउटपुट सही होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
नक्शा डीपी परिभाषित करें
-
हल () नामक एक विधि को परिभाषित करें, यह सिर, जड़ और ध्वज लेगा
-
यदि सिर शून्य है, तो सत्य लौटें, या यदि जड़ शून्य है, तो झूठी वापसी करें
-
अगर dp का एक सिर है, और dp[head] में जड़ है और dp[head, root] का एक झंडा है, तो dp[head, root, flag] लौटाएँ।
-
यदि सिर का मान =मूल का मान, तो
-
ret :=हल करें (सिर के आगे, जड़ के बाएँ, असत्य) या हल करें (सिर के आगे, जड़ के दाएँ, असत्य)
-
यदि रिट सेट है, तो dp[head, root, flag] :=true और return dp[head, root, flag]
-
डीपी [सिर, जड़, झंडा] =हल करें (सिर, जड़ के बाईं ओर, झंडा) या हल करें (सिर, जड़ का अधिकार, झंडा)
-
वापसी डीपी [सिर, जड़, झंडा]
-
-
अन्यथा जब ध्वज सेट नहीं होता है, तो डीपी [सिर, जड़, ध्वज] लौटाएं:=झूठा
-
अन्यथा डीपी [सिर, जड़, ध्वज] लौटाएं:=हल करें (सिर, रूट के बाएं, ध्वज) या हल करें (सिर, रूट का अधिकार, ध्वज)
-
मुख्य विधि से कॉल सॉल्व (हेड, रूट, ट्रू)
उदाहरण (C++)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
map < ListNode*, map<TreeNode*, map <bool, bool>> > dp;
bool solve(ListNode* head, TreeNode* root, bool flag = true){
if(head == NULL) return true;
if(!root) return false;
if(dp.count(head) && dp[head].count(root) && dp[head]
[root].count(flag)) return dp[head][root][flag];
if(head->val == root->val){
bool ret = solve(head->next, root->left, false) ||
solve(head->next, root->right, false);
if(ret) return dp[head][root][flag] = true;
return dp[head][root][flag] = solve(head, root->left,
flag) || solve(head, root->right, flag);
}else if(!flag) return dp[head][root][flag] = false;
else
return dp[head][root][flag]= solve(head, root->left,
flag) || solve(head, root->right, flag);
}
bool isSubPath(ListNode* head, TreeNode* root) {
return solve(head, root);
}
};
main(){
vector<int> v = {1,4,2,6};
vector<int> v1 = {1,4,4,NULL,2,2,NULL,1,NULL,6,8,NULL,NULL,NULL,NULL,1,3};
ListNode *head = make_list(v);
TreeNode *root = make_tree(v1);
Solution ob;
cout << (ob.isSubPath(head, root));
} इनपुट
[1,4,2,6] [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
आउटपुट
1