পাইথনের একটি প্রদত্ত বাইনারি ট্রিতে একটি লিঙ্কযুক্ত তালিকা উপস্থিত আছে কিনা তা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ট্রি দেওয়া হয়েছে যার একটি রুট নোড 'রুট' আছে এবং একটি লিঙ্কযুক্ত তালিকা রয়েছে যার একটি হেড নোড 'হেড' রয়েছে। সেই লিঙ্কযুক্ত তালিকাটি সেই বাইনারি ট্রিতে বিদ্যমান কিনা তা আমাদের খুঁজে বের করতে হবে। যদি গাছের নোডগুলির একটি সেট লিঙ্কযুক্ত তালিকা হিসাবে একে অপরের সাথে লিঙ্ক থাকে এবং যদি সেই ক্রম প্রদত্ত লিঙ্কযুক্ত তালিকার অনুরূপ হয়, তাহলে আমরা 'সত্য' ফেরত দিই বা অন্যথায়, আমরা 'ফলস' ফেরত দিই।

সুতরাং, যদি ইনপুট মত হয়

বৃক্ষ

লিঙ্ক করা তালিকা

তাহলে আউটপুট হবে True।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• arr :=একটি নতুন তালিকা
• size :=arr এর আকার
• temp_arr :=আকারের একটি অ্যারে (আকার + 1) -1 দিয়ে শুরু করা হয়েছে
• একটি ফাংশন সাহায্যকারী() সংজ্ঞায়িত করুন। এই রুট নিতে হবে, val
  • যদি val>=আকার হয়, তাহলে
    • সত্য ফেরান
  • যদি root None-এর মত হয়, তাহলে
    • মিথ্যে ফেরত দিন
  • val :=val + 1
  • যদিও val> 0 এবং রুটের মান arr[val - 1] এর মতো নয়, do
    • val :=temp_arr[val - 1] + 1
  • যদি সাহায্যকারী (মূলের বামে, ভাল) বা সহায়ক (মূলের ডানদিকে, ভাল) সত্য হয়, তাহলে
    • সত্য ফেরান
  • মিথ্যে ফেরত দিন
• শুরু :=মাথা
• যখন শুরু null এর মত নয়, do
  • arr-এর শেষে start-এর মান যোগ করুন
  • start :=শুরুর পরের
• রেঞ্জ 1 থেকে সাইজ + 1 এর মধ্যে নোডের জন্য, করুন
  • temp_arr[নোড] :=temp_arr[নোড - 1] + 1
  • যদিও temp_arr[নোড]> 0 এবং arr[নোড - 1] arr[temp_arr[নোড] - 1] এর মতো নয়, do
    • temp_arr[নোড] :=temp_arr[temp_arr[নোড] - 1] + 1
• রিটার্ন হেল্পার(রুট, 0)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

ক্লাস ট্রিনোড:def __init__(self, val, left=None, right=None):self.val =val self.left =left self.right =rightclass ListNode:def __init__(self, val, next=None) :self.val =val self.next =nextdef insert(temp,data):que =[] que.append(temp) while (len(que)):temp =que[0] que.pop(0) if ( temp.left নয়):যদি ডেটা না হয় None:temp.left =TreeNode(data) else:temp.left =TreeNode(0) break else:que.append(temp.left) if (temp.right নয়):if ডেটা কোনটি নয়:temp.right =TreeNode(data) else:temp.right =TreeNode(0) break else:que.append(temp.right)def make_tree(elements):node =TreeNode(elements[0]) এর জন্য এলিমেন্টে এলিমেন্ট[1:]:ইনসার্ট(নোড, এলিমেন্ট) রিটার্ন নোডেফ মেক_লিস্ট(এলিমেন্টস):হেড =লিস্টনোড(এলিমেন্টস[0]) এলিমেন্টের এলিমেন্টের জন্য[1:]:ptr =হেড যখন ptr.next:ptr =p tr.next ptr.next =ListNode(element) রিটার্ন headdef solve(root, head):arr =[] start =head while start:arr +=(start.val,) start =start.next size =len(arr) temp_arr =[-1] * (আকার + 1) পরিসরে নোডের জন্য (1, আকার + 1):temp_arr[নোড] =temp_arr[নোড - 1] + 1 যখন temp_arr[নোড]> 0 এবং arr[নোড - 1 ] !=arr[temp_arr[নোড] - 1]:temp_arr[node] =temp_arr[temp_arr[node] - 1] + 1 def helper(root, val):if val>=size:return True যদি রুট না হয়:রিটার্ন False val +=1 while val> 0 এবং root.val !=arr[val - 1]:val =temp_arr[val - 1] + 1 যদি helper(root.left, val) অথবা helper(root.right, val) :রিটার্ন ট্রু রিটার্ন ফলস রিটার্ন হেল্পার(রুট, 0)রুট =make_tree([6, 7, 8, 9, 10])head =make_list([6, 7, 10])print(solve(root, head)) 
ইনপুট
 
root =make_tree([6, 7, 8, 9, 10])head =make_list([6, 7, 10])print(solve(root, head))
 
আউটপুট
 
সত্য