পাইথনে অলমোস্ট BST কে এক্সাক্ট BST বানाने প্রোগ্রাম

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

তাই, ইনপুট যদি নিচের ট্রি হয়, তবে আউটপুট হবে সঠিক BST।

সমাধানের ধাপগুলো:

• prev_node := null, min_node := null, max_node := null
• found_one := False
• রুটের ইনঅর্ডার ট্রাভার্সালের প্রতিটি node এর জন্য, করুন
  • যদি prev_node নাল না হয়, তবে
    • যদি node.val < prev_node.val, তবে
      • যদি min_node নাল হয় বা node.val < min_node.val, তবে
        • min_node := node
      • যদি max_node নাল হয় বা max_node.val < prev_node.val, তবে
        • max_node := prev_node
      • যদি found_one ট্রু হয়, তবে
        • লুপ থেকে বের হোন
      • অন্যথায়,
        • found_one := True
    • prev_node := node
• min_node ও max_node-এর ভ্যালু সোয়াপ করুন
• root রিটার্ন করুন

বেশি বুঝতে নিচের বাস্তবায়নটি দেখুন:

উদাহরণ

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,