在平衡 BST 中查找和为给定对

引言

平衡二叉搜索树（BST）是一种高效的数据结构，可提供快速的搜索、插入和删除操作。它们维护元素的排序顺序，这使得它们非常适合高效地解决各种问题。一个常见的问题是在 BST 中查找一对元素，它们的和等于给定值。

理解问题

给定一个平衡 BST 和一个目标和，我们的任务是找到 BST 中和等于给定目标的元素对。我们可以假设 BST 中不存在重复元素。

方法

解决此问题的高效思路在于利用 BST 的特性。由于 BST 以排序顺序维护元素，我们可以通过两种不同的方式遍历它来找到这对元素。

中序遍历 + 双指针

• 对 BST 执行中序遍历，以获取排序的元素。
• 初始化两个指针，一个指向最小元素（最左边），另一个指向最大元素（最右边）。
• 移动这两个指针，同时检查它们所指向元素的和。
• 如果和等于目标，我们就找到了这对元素。如果和小于目标，则将左指针向右移动。如果和大于目标，则将右指针向左移动。
• 重复此过程，直到指针相遇或找到目标和。

使用哈希集

• 在此方法中，我们在遍历 BST 的同时，使用哈希集来维护。
• 哈希集存储在遍历过程中遇到的节点的数值。
• 在遍历 BST 时，对于每个节点，我们检查当前节点的值的补数（即 targetSum - current node value）是否存在于哈希集中。
• 如果存在，我们就找到了和等于目标和的一对元素。

C++ 中的实现

第 1 种方法的实现

说明

• 程序通过包含必要的库并定义 TreeNode 结构来表示二叉树节点，以类似的方式开始。
• 它引入了一个新的辅助函数 inorder，该函数执行 BST 的迭代中序遍历，并将节点存储在堆栈中。此函数有助于高效地按值的顺序检索节点。
• findTarget 函数检查 BST 中是否存在给定和的对。它首先处理根节点为 nullptr 的边缘情况，如果树为空，则立即返回 false。
• 在 findTarget 函数中，初始化了两个堆栈（leftStack 和 rightStack）以按中序顺序存储 BST 的节点。
• 调用 inorder 函数两次，一次用于左子树，一次用于右子树，以按升序将节点填充到堆栈中。
• 将两个指针（left 和 right）初始化为各自堆栈的顶部节点。
• 程序进入一个循环，该循环一直持续到 left 和 right 指向的值交叉，从而确保检查所有可能的对。
• 在循环内，程序计算 left 和 right 指向的值的和。如果 sum 等于目标值 k，则函数返回 true。
• 如果 sum 小于 k，表示当前和小于目标，则程序更新左指针，并用更新后的左节点右子树中的节点重新填充 leftStack。
• 反之，如果 sum 大于 k，表示当前和大于目标，则程序更新右指针，并用更新后的右节点左子树中的节点重新填充 rightStack。
• 最后，如果循环完成而没有找到和为给定和的对，则函数返回 false。
• main 函数通过创建样本 BST，设置目标和，并打印 BST 中是否存在给定和的对来演示 findTarget 函数的用法。

程序输出

第 2 种方法的实现

说明

• 程序通过为 BST 的节点定义结构开始。每个节点包含一个整数值（data）以及指向其左子节点和右子节点的指针（left 和 right）。
• 此外，还提供了一个 createNode() 函数来动态分配新节点的内存并初始化其数据和指针。
• findPair() 函数是程序的核心，负责遍历 BST 并识别具有所需和的节点对。它接受三个参数：当前正在处理的节点（root）、要查找的目标和（targetSum）以及用于存储已访问节点值的无序集的引用（elements）。
• 在 findPair() 函数中，基本情况检查当前节点是否为空，表示一个空子树，在这种情况下，它返回 false。否则，它递归地遍历左子树和右子树。
• 在遍历过程中，函数检查当前节点的值的补数（即 targetSum - root->data）是否存在于已访问元素集中。如果找到，则表示存在和等于目标和的一对元素。在这种情况下，它会打印这对元素并返回 true。
• 如果在集合中未找到补数，则将当前节点的值添加到集合中，从而确保未来的节点可以使用它进行对匹配。
• 在处理完左子树并检查完对之后，函数将继续处理右子树。
• 在 main() 函数中，通过一个值为 15 的根节点创建了一个样本 BST，并添加了其他节点以形成平衡的树结构。为了演示，选择了 33 作为目标和。
• 最后，调用 findPair() 函数，传入 BST 的根节点、目标和以及一个空集以开始搜索对。如果没有找到对，则打印一条消息指示。

程序输出

结论

平衡二叉搜索树 (BST) 证明了这些基本概念的多功能性和效率。通过利用 BST 的固有特性，我们可以设计出有效的解决方案，为这项任务提供最佳的时间复杂度。

方法 1 采用中序遍历和双指针，展示了利用树遍历技术在 BST 中高效导航的优雅之处，并在此过程中识别潜在的对。

另一方面，方法 2 展示了哈希集数据结构的力量，它通过利用哈希来实现遍历过程中的快速查找操作，从而提供了不同的视角。

除了技术细节之外，这些方法的意义还延伸到各个领域的实际应用。无论是金融算法中检测具有特定组合值的投资对至关重要，还是计算生物学中分析基因序列对至关重要，在 BST 中高效查找对的能力都远远超出了纯粹的理论练习。