Cho một cây tìm kiếm nhị phân (BST) chứa giá trị nguyên và một số 'total'. Cần xác định xem có tồn tại ba phần tử trong BST mà tổng của chúng bằng 'total' hay không.
Ví dụ với cây BST như hình và total = 12 → kết quả True.
Thuật toán
- Tạo danh sách rỗng
temp_list. - Duyệt cây theo inorder (trái - gốc - phải) để đưa các giá trị vào
temp_list(danh sách sẽ được sắp xếp). - Với mỗi chỉ số i từ 0 đến len-3:
- left = i+1, right = len-1.
- Trong khi left < right:
- Nếu temp_list[i] + temp_list[left] + temp_list[right] == sum → True.
- Nếu tổng < sum → left++.
- Ngược lại → right--.
- Trả về False nếu không tìm thấy.
Ví dụ code
class TreeNode:
def __init__(self, value):
self.value = value
self.right = None
self.left = None
def traverse_inorder(tree_root, inorder):
if tree_root is None:
return
traverse_inorder(tree_root.left, inorder)
inorder.append(tree_root.value)
traverse_inorder(tree_root.right, inorder)
def solve(tree_root, sum):
temp_list = []
traverse_inorder(tree_root, temp_list)
for i in range(len(temp_list) - 2):
left = i + 1
right = len(temp_list) - 1
while left < right:
current = temp_list[i] + temp_list[left] + temp_list[right]
if current == sum:
return True
elif current < sum:
left += 1
else:
right -= 1
return False
# Xây dựng cây ví dụ
tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)
print(solve(tree_root, 12))
Đầu vào
Cây BST như trên, total = 12
Đầu ra
True