วิธีตรวจสอบว่า Binary Tree เป็น Valid Binary Search Tree ด้วย Recursion ใน C#

Tree เป็น Binary Search Tree หากมีลูกซ้ายทั้งหมดน้อยกว่าองค์ประกอบของ node และลูกขวาทั้งหมดมากกว่าองค์ประกอบของ node เริ่มต้นเราตรวจสอบว่า node มีค่าหรือไม่ หาก node เป็น null ถือว่าเป็น valid BST และคืนค่า true หลังจากตรวจสอบ node null แล้ว เราเรียกเมธอด isValidBST แบบ recursive โดยส่ง node, min value และ max value หากค่า root น้อยกว่าหรือเท่ากับ min และค่า root มากกว่าหรือเท่ากับ max ถือว่าไม่ใช่ BST คืนค่า false มิฉะนั้นเรียก isValidBST ซ้ำโดยส่งค่าลูกซ้ายและลูกขวาจนตรวจสอบทุก node

ตัวอย่าง

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