Kiểm tra xem bộ ba với tổng đã cho có tồn tại trong BST bằng Python hay không

Giả sử, chúng ta được cung cấp Cây tìm kiếm nhị phân (BST) chứa các giá trị nguyên và một số 'tổng'. Chúng tôi phải tìm xem có bất kỳ nhóm ba phần tử nào trong BST đã cung cấp mà phép cộng ba phần tử bằng giá trị 'tổng' đã cung cấp hay không.

Vì vậy, nếu đầu vào giống như

tổng =12, thì kết quả đầ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 -

• temp_list:=một danh sách mới được khởi tạo bằng 0
• inorder đi ngang qua cái cây và đưa nó vào temp_list
• đối với tôi trong phạm vi 0 đến (kích thước của temp_list - 2), tăng 1, thực hiện
  • trái:=i + 1
  • right:=kích thước của temp_list - 1
  • khi left
  • nếu temp_list [i] + temp_list [left] + temp_list [right] giống với sum thì
    • trả về True
  • ngược lại khi temp_list [i] + temp_list [left] + temp_list [right]
  • left:=left + 1
• nếu không,
  • right:=right - 1

Ví dụ

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

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

Đầu ra

True