Cách kiểm tra cây nhị phân có phải BST hợp lệ bằng đệ quy C#

Cây là BST nếu tất cả con trái nhỏ hơn nút, con phải lớn hơn nút. Kiểm tra nút null → true. Gọi đệ quy isValidBST với node, min, max. Nếu giá trị nút ≤ min hoặc ≥ max → false. Ngược lại đệ quy con trái (min, node.Value) và con phải (node.Value, max).

Ví dụ

public class TreesPgm
{
    public class Node
    {
        public int Value;
        public Node LeftChild;
        public Node RightChild;
        public Node(int value)
        {
            this.Value = value;
        }
        public override String ToString()
        {
            return "Node=" + Value;
        }
    }

    public bool IsValidBST(Node root)
    {
        if (root == null)
        {
            return true;
        }
        return IsValidBST(root, int.MinValue, int.MaxValue);
    }

    private bool IsValidBST(Node root, int min, int max)
    {
        if (root == null)
        {
            return true;
        }
        if (root.Value <= min || root.Value >= max)
        {
            return false;
        }
        return IsValidBST(root.LeftChild, min, root.Value) && IsValidBST(root.RightChild, root.Value, max);
    }
}

Đầu vào

Kết quả

True

Giải thích: Xác thực BST bằng đệ quy với khoảng giá trị cho phép (min, max). Gốc 5: trái <5, phải >5. Nút 2: trái <2, phải trong (2,5). Nút 6: phải >6. Cây ví dụ thỏa mãn BST. O(n) thời gian.