পাইথনে দিকনির্দেশের তালিকা ব্যবহার করে বাইনারি ট্রি অতিক্রম করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ট্রি এবং "R"(ডান), "L"(বাম) এবং "U"(উপর) সমন্বিত স্ট্রিং মুভের একটি তালিকা আছে। শিকড় থেকে শুরু করে, আমাদের প্রতিটি চালে সঞ্চালন করে গাছটি অতিক্রম করতে হবে যেখানে:"R" সঠিক সন্তানের দিকে ট্র্যাভার্স নির্দেশ করে। "L" বাম সন্তানের ট্র্যাভার্স নির্দেশ করে। "U" তার অভিভাবককে ট্র্যাভার্স নির্দেশ করে।

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

["R","R","U","L"], তাহলে আউটপুট হবে 3

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

• অতীত :=একটি নতুন তালিকা

• প্রতিটি পদক্ষেপের জন্য, করুন

  • অতীতের শেষে রুট সন্নিবেশ করান

  • যদি সরানো হয় "L" এর মতো, তাহলে

    • root :=রুটের বাম

  • অন্যথায় যখন সরানো হয় "R" এর মতো, তারপর

    • root :=রুটের ডানদিকে

  • অন্যথায়,

    • অতীত থেকে শেষ উপাদান মুছুন

    • root :=অতীত থেকে শেষ উপাদান এবং অতীত থেকে এটি মুছে দিন

• রুটের রিটার্ন মান

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

উদাহরণ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, moves):
      past = []
      for move in moves:
         past.append(root)
         if move == "L":
            root = root.left
         elif move == "R":
            root = root.right
         else:
            past.pop()
            root = past.pop()
      return root.val
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
traverse = ["R","R","U","L"]
print(ob.solve(root, traverse))

ইনপুট

root = TreeNode(2) root.right = TreeNode(4) root.right.left =
TreeNode(3) root.right.right = TreeNode(5) ["R","R","U","L"]

আউটপুট

3