สมมติว่ามี BST และค่า low, high เราต้องลบโหนดทั้งหมดที่ไม่อยู่ในช่วง [low, high] (รวม)
เช่น ถ้าอินพุตเป็นต้นไม้ดังภาพ low = 7, high = 10 ผลลัพธ์จะเป็นต้นไม้ที่เหลือโหนด 7,8,9,10
ขั้นตอนการแก้ปัญหา
- กำหนดฟังก์ชัน solve() รับ root, low, high
- ถ้า root เป็น null คืนค่า None
- ถ้า low > root.data คืนค่า solve(right of root, low, high)
- ถ้า high < root.data คืนค่า solve(left of root, low, high)
- right of root := solve(right of root, low, high)
- left of root := solve(left of 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,
