โปรแกรมตรวจสอบว่าต้นไม้ไบนารีเป็น BST หรือไม่ใน Python

สมมติว่ามีต้นไม้ไบนารี เราต้องตรวจสอบว่ามันเป็นต้นไม้ค้นหาไบนารี (BST) หรือไม่ BST มีคุณสมบัติ

• โหนดทั้งหมดในซับทรีนซ้ายมีค่าน้อยกว่าโหนดปัจจุบัน
• โหนดทั้งหมดในซับทรีนขวามีค่ามากกว่าโหนดปัจจุบัน
• คุณสมบัตินี้เป็นจริงแบบเรียกซ้ำสำหรับทุกโหนด

เช่น ถ้าอินพุตเป็นต้นไม้ดังภาพ ผลลัพธ์จะเป็น True

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

• x := รายการลำดับ inorder traversal ของต้นไม้
• ถ้า x เรียงลำดับแล้ว คืนค่า true มิฉะนั้น false

ตัวอย่างโค้ด

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

class Solution:
    def solve(self, root):
        def inorder(root, l):
            if root is None:
                return
            inorder(root.left, l)
            l.append(root.data)
            inorder(root.right, l)
        l = []
        inorder(root, l)
        return l == sorted(l)

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

อินพุต

root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)

เอาต์พุต

True