Chương trình xóa nút BST ngoài khoảng cho trước trong Python

Cho BST và hai giá trị low, high, xóa tất cả nút không nằm trong khoảng [low, high].

Ví dụ

Cây đầu vào: (hình ảnh), low=7, high=10.
Cây sau khi xóa: (hình ảnh).

Thuật toán

1. Đệ quy solve(root, low, high):
   • Nếu root là None, trả về None.
   • Nếu low > root.data: trả về solve(root.right, low, high).
   • Nếu high < root.data: trả về solve(root.left, low, high).
   • Ngược lại: đệ quy cập nhật root.left và root.right, trả về root.

Mã nguồn Python

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 / Đầu ra

Input: root = TreeNode(5) ..., low=7, high=10
Output: 7, 8, 9, 10,