Kiểm tra tính hợp lệ của Cây nhị phân tìm kiếm

Mục tiêu kiến thức

• Hiểu định nghĩa đầy đủ của Cây nhị phân tìm kiếm (BST): mọi nút trong cây con bên trái phải nhỏ hơn nút gốc, và mọi nút trong cây con bên phải phải lớn hơn nút gốc.
• Nhận diện sai lầm phổ biến: chỉ so sánh cục bộ giữa nút cha và hai con trực tiếp.
• Sử dụng kỹ thuật truyền cận (min_val, max_val) trong đệ quy duyệt cây.

Mô tả bài toán

Trong hệ thống chỉ mục tìm kiếm tài liệu của AI Empire Academy, dữ liệu chỉ mục được cấu trúc dưới dạng Cây nhị phân tìm kiếm (BST). Một cây nhị phân được coi là BST hợp lệ nếu và chỉ nếu:

• Cây con bên trái của một nút chỉ chứa các nút có giá trị nhỏ hơn nghiêm ngặt giá trị của nút đó.
• Cây con bên phải của một nút chỉ chứa các nút có giá trị lớn hơn nghiêm ngặt giá trị của nút đó.
• Cả hai cây con trái và phải đều phải là cây nhị phân tìm kiếm hợp lệ.
• Cây rỗng (None) được coi là BST hợp lệ.

Cho một cây nhị phân với nút gốc root. Hãy viết hàm is_valid_bst(root: TreeNode | None) -> bool kiểm tra xem cây có phải là BST hợp lệ hay không.

Lớp TreeNode được định nghĩa sẵn như sau:

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

Ràng buộc

• Số lượng nút trong cây từ 0 đến 10⁴.
• -2³¹ ≤ Node.val ≤ 2³¹ - 1.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.