ধরুন আমাদের কাছে একটি বাইনারি ট্রি রুট এবং প্রথম নোড হিসাবে একটি হেড সহ একটি লিঙ্কযুক্ত তালিকা রয়েছে। হেড থেকে শুরু করে লিঙ্ক করা তালিকার সমস্ত উপাদান যদি বাইনারি ট্রিতে সংযুক্ত কিছু নিম্নগামী পথের সাথে মিলে যায় তাহলে আমাদের সত্যে ফিরতে হবে অন্যথায় False। তাই গাছটি যদি −
এর মত হয় 
এবং লিঙ্ক করা তালিকা হল [1,4,2,6], তাহলে আউটপুট সত্য হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র ডিপি
সংজ্ঞায়িত করুন -
সমাধান() নামক একটি পদ্ধতি নির্ধারণ করুন, এটি মাথা, রুট এবং পতাকা গ্রহণ করবে
-
যদি হেড নাল হয়, তাহলে true ফেরত দিন, অথবা যদি রুটটি নাল হয়, তাহলে false ফেরত দিন
-
যদি dp-এর হেড থাকে, এবং dp[head]-এর রুট থাকে এবং dp[head, root]-এর একটি পতাকা থাকে, তাহলে dp[head, root, flag]
-
যদি মাথার মান =মূলের মান, তাহলে
-
ret :=সমাধান (মাথার পাশে, মূলের বামে, মিথ্যা) বা সমাধান (মাথার পাশে, মূলের ডানদিকে, মিথ্যা)
-
যদি ret সেট করা হয়, তাহলে dp[head, root, flag] :=true এবং return dp[head, root, flag]
-
dp[head, root, flag] =solve(head, root এর বাম, পতাকা) অথবা solve(head, root এর ডান, পতাকা)
-
রিটার্ন dp[head, root, flag]
-
-
অন্যথায় যখন পতাকা সেট করা না থাকে, তখন dp[head, root, flag] :=false
রিটার্ন করুন -
অন্যথায় dp[head, root, flag] ফেরত দিন :=solve(head, root এর বাম, পতাকা) অথবা solve(head, root এর ডান, পতাকা)
-
মূল পদ্ধতি থেকে কল সমাধান (হেড, রুট, সত্য)
উদাহরণ (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
