Chương trình kiểm tra giá trị có tồn tại trong cây BST hay không trong Python

Cho cây tìm kiếm nhị phân (BST) và giá trị val, kiểm tra xem val có trong cây hay không.

Ví dụ (cây minh họa): val = 7, đầu ra True.

Các bước giải quyết (đệ quy):

• Nếu root là None, trả về False.
• Nếu root.data == val, trả về True.
• Nếu root.data > val, tìm ở cây con trái.
• Ngược lại, tìm ở cây con phải.

Ví dụ minh họa

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, val):
        if not root:
            return False
        if root.data == val:
            return True
        if root.data > val:
            return self.solve(root.left, val)
        return self.solve(root.right, val)

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

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

Đầu ra

True