ให้ Binary Search Tree และค่า val ตรวจสอบว่า val อยู่ในต้นไม้หรือไม่
คุณสมบัติ BST: โหนดซ้าย < ราก < โหนดขวา → ค้นหาได้ใน O(h)
อัลกอริธึม Recursive
- ถ้า root เป็น None → False
- ถ้า root.val == val → True
- ถ้า root.val > val → ค้นหาด้านซ้าย, มิฉะนั้น ค้นหาด้านขวา
การนำไปใช้
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)) # True
