পাইথনে প্রায় বিএসটি থেকে সঠিক বিএসটি করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ট্রি আছে এবং সেটি প্রায় একটি বাইনারি সার্চ ট্রি। শুধুমাত্র দুটি নোডের মান অদলবদল করা হয়। আমাদের এটি সংশোধন করতে হবে এবং বাইনারি সার্চ ট্রি ফেরত দিতে হবে।

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

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

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

• prev_node :=null, min_node :=null, max_node :=null
• found_one :=মিথ্যা
• রুটের অভ্যন্তরীণ ট্রাভার্সালের প্রতিটি নোডের জন্য, করুন
  • যদি prev_node null না হয়, তাহলে
    • যদি নোডের মান
    • যদি min_node নাল হয় বা node এর মান
    • মিন_নোড :=নোড
  • যদি max_node নাল হয় বা max_node এর মান
  • max_node :=prev_node
• যদি পাওয়া_একটি সত্য হয়, তাহলে
  • লুপ থেকে বেরিয়ে আসুন
• অন্যথায়,
  • found_one :=সত্য

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

উদাহরণ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
     
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.val, end = ', ')
      print_tree(root.right)
   
def __iter__(self):
   if self.left:
      for node in self.left:
         yield node
   yield self
   if self.right:
      for node in self.right:
         yield node

setattr(TreeNode, "__iter__", __iter__)
class Solution:
   def solve(self, root):
      prev_node = None
      min_node = None
      max_node = None
      found_one = False
      for node in root:
         if prev_node:
            if node.val < prev_node.val:
               if min_node is None or node.val < min_node.val:
                  min_node = node
               if max_node is None or max_node.val < prev_node.val:
                  max_node = prev_node
               if found_one:
                  break
               else:
                  found_one = True
         prev_node = node
      min_node.val, max_node.val = max_node.val, min_node.val
      return root
     
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(6)
root.right = TreeNode(8)
root.right.left = TreeNode(2)
root.right.right = TreeNode(9)
print_tree(ob.solve(root))

ইনপুট

root = TreeNode(3)
root.left = TreeNode(6)
root.right = TreeNode(8)
root.right.left = TreeNode(2)
root.right.right = TreeNode(9)

আউটপুট

2, 3, 6, 8, 9,