अजगर में लगभग बीएसटी से सटीक बीएसटी बनाने का कार्यक्रम

मान लीजिए हमारे पास एक बाइनरी ट्री है और वह लगभग एक बाइनरी सर्च ट्री है। केवल दो नोड्स के मान की अदला-बदली की जाती है। हमें इसे ठीक करना होगा और बाइनरी सर्च ट्री को वापस करना होगा।

तो, अगर इनपुट पसंद है

तो आउटपुट होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• prev_node:=null, min_node:=null, max_node:=null
• मिला_एक:=झूठा
• रूट के इनऑर्डर ट्रैवर्सल में प्रत्येक नोड के लिए, करें
  • यदि prev_node रिक्त नहीं है, तो
    • यदि नोड का मान
    • यदि min_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,