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
- 如果 temp_list[i] + temp_list[left] + temp_list[right] 等于 sum,则
- 返回 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
Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.
输出
True
广告