โจทย์: กำหนด Binary Search Tree (BST) ที่มีค่า Integer และค่า 'total' ตรวจสอบว่ามี Triplet (3 โหนด) ใดใน BST ที่ผลรวมเท่ากับ total หรือไม่
ตัวอย่าง
total = 12 → Output: True
แนวทางแก้ปัญหา
- Inorder Traversal BST → ได้รายการเรียงลำดับ (Sorted List)
- ใช้ Two-pointer Technique หา Triplet Sum ใน Sorted Array:
- วน i จาก 0 ถึง n-3
- left = i+1, right = n-1
- while left < right:
- ถ้า sum == target → True
- ถ้า sum < target → left++
- ถ้า sum > target → right--
- ไม่พบ → False
โค้ดตัวอย่าง
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 = [0]
traverse_inorder(tree_root, temp_list)
for i in range(0, len(temp_list) - 2, 1):
left = i + 1
right = len(temp_list) - 1
while left < right:
if temp_list[i] + temp_list[left] + temp_list[right] == sum:
return True
elif temp_list[i] + temp_list[left] + temp_list[right] < sum:
left += 1
else:
right -= 1
return False
# สร้าง BST ตัวอย่าง
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))
Input / Output
Input: BST (5,3,7,2,4,6,8), total=12 Output: True
