मान लीजिए हमारे पास एक बाइनरी ट्री रूट और एक लिंक्ड लिस्ट है जिसका हेड पहला नोड है। हमें True लौटाना है अगर लिंक्ड लिस्ट में हेड से शुरू होने वाले सभी एलिमेंट्स बाइनरी ट्री में किसी डाउनवर्ड पथ से मेल खाते हैं, अन्यथा False। उदाहरण के लिए, अगर ट्री है:
और लिंक्ड लिस्ट [1,4,2,6] है, तो आउटपुट true होगा।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
एक मैप dp डिफाइन करें
solve() नाम का एक मेथड डिफाइन करें, जो head, root, और flag लेगा
अगर हेड नल है, तो true लौटाएं, या अगर रूट नल है, तो false लौटाएं
अगर dp में हेड है, और dp[head] में रूट है और dp[head][root] में flag है, तो dp[head][root][flag] लौटाएं
अगर हेड का वैल्यू = रूट का वैल्यू, तो:
ret := solve(हेड का नेक्स्ट, रूट का लेफ्ट, false) या solve(हेड का नेक्स्ट, रूट का राइट, false)
अगर ret सेट है, तो dp[head][root][flag] := true और dp[head][root][flag] लौटाएं
dp[head][root][flag] = solve(head, root का लेफ्ट, flag) OR solve(head, root का राइट, flag)
dp[head][root][flag] लौटाएं
अन्यथा जब flag सेट नहीं है, तो dp[head][root][flag] := false लौटाएं
अन्यथा dp[head][root][flag] := solve(head, root का लेफ्ट, flag) या solve(head, root का राइट, flag) लौटाएं
मेन मेथड से solve(head, root, true) कॉल करें
उदाहरण (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);
}
};
int 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
