पायथन में BST से रेंज में नहीं आने वाले सभी नोड्स को हटाने का प्रोग्राम

मान लीजिए हमारे पास एक BST है, और दो मान low और high हैं, हमें उन सभी नोड्स को हटाना है जो [low, high] (सम्मिलित) के बीच नहीं हैं।

उदाहरण के लिए, यदि इनपुट जैसा है: low = 7, high = 10, तो आउटपुट होगा:

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

• solve() फंक्शन परिभाषित करें जो root, low, high लेता है
• यदि root null है, तो वापस करें
• यदि low > root का डेटा, तो solve(root का दायां, low, high) वापस करें
• यदि high < root का डेटा, तो solve(root का बायां, low, high) वापस करें
• root का दायां := solve(root का दायां, low, high)
• root का बायां := solve(root का बायां, low, high)
• root वापस करें

उदाहरण

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution:
    def solve(self, root, low, high):
        if not root:
            return
        if low > root.data:
            return self.solve(root.right, low, high)
        if high < root.data:
            return self.solve(root.left, low, high)
        root.right = self.solve(root.right, low, high)
        root.left = self.solve(root.left, low, high)
        return root

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
low = 7
high = 10
ret = ob.solve(root, low, high)
print_tree(ret)

इनपुट

root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) low = 7 high = 10

आउटपुट

7, 8, 9, 10,