Python में लगभग BST को सटीक BST में बदलने का प्रोग्राम

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

इसलिए, यदि इनपुट इस तरह है

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

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

• prev_node := null, min_node := null, max_node := null
• found_one := False
• रूट के इनऑर्डर ट्रैवर्सल में प्रत्येक नोड के लिए, करें
  • यदि prev_node null नहीं है, तो
    • यदि नोड का मान < prev_node का मान, तो
      • यदि min_node null है या नोड का मान < min_node का मान, तो
        • min_node := नोड
      • यदि max_node null है या max_node का मान < prev_node का मान, तो
        • max_node := prev_node
      • यदि found_one सत्य है, तो
        • लूप से बाहर आएं
      • अन्यथा,
        • found_one := True
    • prev_node := नोड
• min_node और max_node के मानों को स्वैप करें
• रूट लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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,