ধরুন আমাদের একটি বাইনারি ট্রি রুট এবং একটি লিংকড লিস্ট আছে যার হেড প্রথম নোড। যদি লিংকড লিস্টের সকল এলিমেন্ট হেড থেকে শুরু করে বাইনারি ট্রিতে কোনো ডাউনওয়ার্ড পাথের সাথে মিলে যায়, তবে True রিটার্ন করুন, অন্যথায় False। ট্রি যদি নিচের মতো হয় −
এবং লিংকড লিস্ট [1,4,2,6] হলে আউটপুট হবে true।
সমাধানের ধাপগুলো:
একটি map dp ডিফাইন করুন
solve() মেথড ডিফাইন করুন, যা head, root, flag নেবে
যদি head null হয়, তবে true রিটার্ন করুন; অথবা root null হলে false
যদি dp-তে head, root, flag থাকে, তবে dp[head][root][flag] রিটার্ন করুন
যদি head-এর ভ্যালু == root-এর ভ্যালু হয়, তবে
ret := solve(head->next, root->left, false) OR solve(head->next, root->right, false)
যদি ret সেট হয়, তবে dp[head][root][flag] := true এবং রিটার্ন করুন
dp[head][root][flag] = solve(head, root->left, flag) OR solve(head, root->right, flag)
dp[head][root][flag] রিটার্ন করুন
অন্যথায় যখন flag সেট নয়, তবে dp[head][root][flag] := false রিটার্ন করুন
অন্যথায় dp[head][root][flag] := solve(head, root->left, flag) OR solve(head, root->right, 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); } }; 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
