Validate Binary Search Tree

Bài toán

Cho một cây nhị phân, kiểm tra xem nó có phải là BST hợp lệ không. Quy tắc BST hợp lệ:

• Cây con trái chứa các node có giá trị nhỏ hơn root.
• Cây con phải chứa các node có giá trị lớn hơn root.
• Cả hai cây con trái và phải cũng phải là BST.

Lỗi phổ biến: Check root.left.val < root.val là chưa đủ. Vì toàn bộ cây con bên phải phải lớn hơn root (ví dụ: cây [5, 1, 6, null, null, 3, 7] -> Sai vì con phải chứa số 3 < 5).

Phân Tích & Tiếp Cận

DFS với Bounds (Giới hạn)

Mỗi khi đi xuống một nhánh, ta mang theo một khoảng giá trị (min, max) mà node con BẮT BUỘC phải nằm trong đó.

• Root: (-Inf, +Inf).
• Đi sang Trái của node X: Giới hạn mới là (oldMin, X.val). (Mọi con cháu trái phải nhỏ hơn X).
• Đi sang Phải của node X: Giới hạn mới là (X.val, oldMax). (Mọi con cháu phải lớn hơn X).

Nếu giá trị node hiện tại vi phạm giới hạn -> false.

function isValidBST(root: TreeNode | null): boolean {
    
    function validate(node: TreeNode | null, min: number, max: number): boolean {
        if (!node) return true;

        if (node.val <= min || node.val >= max) {
            return false;
        }

        // Left child: Phải bé hơn node.val hiện tại, và lớn hơn min cũ
        // Right child: Phải lớn hơn node.val hiện tại, và bé hơn max cũ
        return validate(node.left, min, node.val) && 
               validate(node.right, node.val, max);
    }

    return validate(root, -Infinity, Infinity);
}

• Time Complexity: $O(n)$.
• Space Complexity: $O(h)$.

Pattern Nhận Diện

Để validate một cấu trúc cây có ràng buộc cha-con diện rộng (tổ tiên ảnh hưởng hậu duệ), hãy truyền thông tin (Context/Constraints) xuống thông qua tham số đệ quy.