Chương trình xóa tất cả các nút khỏi BST không nằm trong phạm vi bằng Python

Giả sử chúng ta có một BST, hai giá trị thấp và cao, chúng ta phải xóa tất cả các nút không nằm giữa [thấp, cao] (bao gồm).

Vì vậy, nếu đầu vào giống như

low =7 high =10, thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm giải quyết (). Điều này sẽ bắt rễ, thấp, cao
• nếu gốc là null, thì
  • trở lại
• if low> dữ liệu của root, then
  • trả về giải quyết (quyền gốc, thấp, cao)
• if high
• trả về giải quyết (bên trái của thư mục gốc, thấp, cao)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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)

Đầu vào

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

Đầu ra

7, 8, 9, 10,