Cây là một cây tìm kiếm nhị phân nếu nó có tất cả các phần tử con bên trái nhỏ hơn các phần tử nút và tất cả các phần tử con bên phải lớn hơn các phần tử nút. Ban đầu ta kiểm tra xem nút có giá trị nào không, nếu nút là null thì ta coi như cây tìm kiếm nhị phân hợp lệ và trả về true. Sau khi kiểm tra kết quả null của nút, chúng ta gọi phương thức đệ quy isValidBST bằng cách truyền vào nút, giá trị min và giá trị max. Nếu giá trị gốc nhỏ hơn min và giá trị gốc lớn hơn max, chúng tôi coi như không phải là cây tìm kiếm nhị phân và trả về false, chúng tôi gọi phương thức isValidBST một cách đệ quy bằng cách chuyển giá trị bên trái và bên phải cho đến khi nó kiểm tra tất cả các nút
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
5 2 6 1 3
Đầu ra
True