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

Giả sử chúng ta có cây nhị phân; chúng ta phải kiểm tra xem nó có phải là cây tìm kiếm nhị phân hay không. Như chúng ta biết BST có các thuộc tính sau -

• tất cả các nút trên cây con bên trái của nó nhỏ hơn giá trị nút hiện tại
• tất cả các nút trên cây con bên phải của nó lớn hơn giá trị nút hiện tại
• các thuộc tính này giữ một cách đệ quy cho tất cả các nút

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• x:=danh sách trình tự duyệt qua nhỏ hơn của các phần tử cây
• nếu x được sắp xếp, thì
  • trả về true
• trả về false

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

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)

Đầu ra

True