โปรแกรมลบโหนดทั้งหมดออกจาก BST ที่ไม่อยู่ในช่วงใน Python

สมมติว่าเรามี BST สองค่าต่ำและสูง เราต้องลบโหนดทั้งหมดที่ไม่อยู่ระหว่าง [ต่ำ สูง] (รวม)

ดังนั้นหากอินพุตเป็นแบบ

ต่ำ =7 สูง =10 แล้วผลลัพธ์จะเป็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน Solve() สิ่งนี้จะหยั่งราก ต่ำ สูง
• ถ้ารูทเป็นโมฆะ
  • คืนสินค้า
• ถ้าต่ำ> ข้อมูลของรูทแล้ว
  • ผลตอบแทนการแก้(ทางขวาของรูท ต่ำ สูง)
• ถ้าสูง <ข้อมูลของ 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,