Python 中檢查 BST 中是否存在具有給定和的三元組

假設，我們提供了一個包含整數值的二叉搜尋樹 (BST) 和一個數字“total”。我們需要找出提供的 BST 中是否存在任何三個元素的組合，其中這三個元素的總和等於提供的“total”值。

因此，如果輸入類似於

total = 12，則輸出將為 True。

要解決此問題，我們將遵循以下步驟：

  • temp_list := 初始化為零的新列表
  • 中序遍歷樹並將其放入 temp_list 中
  • 對於 i 從 0 到 (temp_list 的大小 - 2)，遞增 1，執行以下操作
    • left := i + 1
    • right := temp_list 的大小 - 1
    • 當 left < right 時，執行以下操作
      • 如果 temp_list[i] + temp_list[left] + temp_list[right] 等於 sum，則
        • 返回 True
      • 否則，當 temp_list[i] + temp_list[left] + temp_list[right] < sum 不為零時，則
        • left := left + 1
      • 否則，
        • right := right - 1
  • 返回 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
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))

輸入

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

輸出

True

更新於： 2021 年 1 月 18 日

111 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告