ต้นไม้เป็นแผนผังการค้นหาแบบไบนารีหากมีลูกด้านซ้ายทั้งหมดน้อยกว่าองค์ประกอบโหนดและชายด์ที่ถูกต้องทั้งหมดมากกว่าองค์ประกอบโหนด เริ่มแรก เราตรวจสอบว่าโหนดมีค่าใด ๆ หรือไม่ หากโหนดนั้นเป็นโมฆะ เราจะพิจารณาว่าเป็นแผนผังการค้นหาไบนารีที่ถูกต้องและคืนค่าเป็นจริง หลังจากตรวจสอบผลลัพธ์ที่เป็นโมฆะของโหนดแล้ว เราจะเรียกเมธอดแบบเรียกซ้ำ isValidBST โดยส่งโหนด ค่าต่ำสุด และค่าสูงสุด หากค่ารูทน้อยกว่าค่าต่ำสุดและค่ารูทมากกว่าค่าสูงสุด เราจะถือว่าไม่ใช่โครงสร้างการค้นหาแบบไบนารีและคืนค่าเป็นเท็จ เราจะเรียกเมธอด isValidBST ซ้ำๆ โดยส่งค่าซ้ายและขวาจนกว่าจะตรวจสอบโหนดทั้งหมด
ตัวอย่าง
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);
}
} อินพุต
5 2 6 1 3
ผลลัพธ์
True
