Xác thực cây tìm kiếm nhị phân bằng Python

Giả sử chúng ta có một cây nhị phân, hãy xác định để kiểm tra xem nó có phải là cây tìm kiếm nhị phân hợp lệ (BST) hay không. Giả sử một BST được định nghĩa như sau -

• Cây con bên trái của một nút chỉ chứa các nút có khóa nhỏ hơn khóa của nút đó.
• Cây con bên phải của một nút chỉ chứa các nút có khóa lớn hơn khóa của nút đó.
• Cả cây con bên trái và bên phải cũng phải là cây tìm kiếm nhị phân.

Vì vậy, nếu cây giống -

Đầ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 -

• Tạo một hàm đệ quy có tên là giải quyết (), hàm này sẽ có giá trị gốc, min và max, phương thức sẽ giống như sau
• nếu root là null, thì trả về true
• nếu giá trị của root <=min hoặc value của root> =max, thì trả về false
• trả về (giải quyết (bên trái của gốc, tối thiểu, giá trị gốc) VÀ giải quyết (bên phải của gốc, giá trị gốc, tối đa))
• ban đầu gọi phương thức giải quyết () bằng cách chuyển root và - inf là min và inf là max.

Ví dụ (Python)

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

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

Đầu vào

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

Đầu ra

true
false