Chương trình kiểm tra cây nhị phân có phải BST không trong Python

Cho cây nhị phân, kiểm tra xem có phải cây tìm kiếm nhị phân (BST) không. BST thỏa mãn: nút trái < nút gốc < nút phải, và tính chất đệ quy.

Ví dụ

Cây đầu vào: (hình ảnh).
Đầu ra: True.

Thuật toán

1. Thực hiện duyệt inorder, lưu giá trị vào danh sách x.
2. Kiểm tra x có được sắp xếp tăng dần không.
3. Trả về True nếu đã sắp xếp, ngược lại False.

Mã nguồn Python

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))

Đầu vào / Đầu ra

Input: root = TreeNode(5) ...
Output: True