ตรวจสอบ Binary Search Tree ใน Python

สมมติว่าเรามีต้นไม้ไบนารี ให้ตรวจสอบว่ามันเป็น binary search tree (BST) ที่ถูกต้องหรือไม่ สมมติว่า BST ถูกกำหนดดังนี้

• ซับทรีด้านซ้ายของโหนดมีเฉพาะโหนดที่มีคีย์น้อยกว่าคีย์ของโหนด
• ซับทรีด้านขวาของโหนดมีเฉพาะโหนดที่มีคีย์มากกว่าคีย์ของโหนด
• ซับทรีซ้ายและขวาทั้งสองต้องเป็น binary search trees ด้วย

ตัวอย่าง ต้นไม้เป็นดังนี้

ผลลัพธ์จะเป็น true

ขั้นตอนการแก้ปัญหา

• สร้างฟังก์ชันเวียนเกิดชื่อ solve() ซึ่งรับ root, min และ max เมธอดจะเป็นดังนี้
• ถ้า root เป็น null ให้คืนค่า true
• ถ้าค่าของ root <= min หรือค่าของ root >= max ให้คืนค่า false
• คืนค่า (solve(ซ้ายของ root, min, ค่า root) AND solve(ขวาของ root, ค่า root, max))
• เรียกเมธอด solve() เริ่มต้นโดยส่ง root, และ -inf เป็น min และ inf เป็น max

ตัวอย่าง (Python):

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

class TreeNode: 
    def __init__(self, data, left = None, right = None): 
        self.data = data 
        self.left = left 
        self.right = right 

def insert(temp, data): 
    que = [] 
    que.append(temp) 
    while (len(que)): 
        temp = que[0] 
        que.pop(0) 
        if (not temp.left): 
            if data is not None: 
                temp.left = TreeNode(data) 
            else: 
                temp.left = TreeNode(0) 
            break 
        else: 
            que.append(temp.left) 
        if (not temp.right): 
            if data is not None: 
                temp.right = TreeNode(data) 
            else: 
                temp.right = TreeNode(0) 
            break 
        else: 
            que.append(temp.right) 

def make_tree(elements): 
    Tree = TreeNode(elements[0]) 
    for element in elements[1:]: 
        insert(Tree, element) 
    return Tree 

class Solution(object): 
    def isValidBST(self, root): 
        return self.solve(root, -1000000000000000000000, 1000000000000000000000) 
    
    def solve(self, root, min_val, max_val): 
        if root == None or root.data == 0: 
            return True 
        if (root.data <= min_val or root.data >= max_val): 
            return False 
        return self.solve(root.left, min_val, root.data) and self.solve(root.right, root.data, max_val) 

ob1 = Solution() 
tree = make_tree([3,1,4,None,2,None,5]) 
print(ob1.isValidBST(tree)) 
tree = make_tree([5,1,4,None,None,3,6]) 
print(ob1.isValidBST(tree))

อินพุต

[3,1,4,null,2,null,5] [5,1,4,null,null,3,6]

เอาต์พุต

true false