力扣 653. 两数之和 IV - 二叉树 / Binary Tree Two-Sum IV

题目描述

给定一个二叉搜索树（BST）和一个目标值 k，请你实现一个函数 findTarget，它返回二叉搜索树中是否存在两个节点，它们的值的和等于目标值 k。

示例 1:

输入:

plaintextCopy Code
root = [5,3,6,2,4,null,7], k = 9

输出:

plaintextCopy Code
true

解释:

Copy Code
因为 2 + 7 = 9

示例 2:

输入:

plaintextCopy Code
root = [5,3,6,2,4,null,7], k = 28

输出:

plaintextCopy Code
false

解释:

Copy Code
没有两个节点的值的和是28

说明:

• 树中的节点的值是正整数。
• 你可以假设二叉搜索树中每个节点的值都是唯一的。

解题思路

1. 问题分析

给定一个二叉搜索树，我们需要在其中寻找两个不同的节点，它们的值之和等于目标值 k。这类问题本质上就是在搜索树中找到两个节点对，符合特定的条件。在二叉搜索树中，由于其结构的特殊性（左子树节点值小于根节点，右子树节点值大于根节点），我们可以利用这个性质来优化查找过程。

2. 解法一：中序遍历 + 哈希集

通过对二叉搜索树进行中序遍历，我们可以得到一个有序的节点值列表。然后，我们可以使用哈希集合来记录我们已经访问过的节点值，以便在访问当前节点时，我们可以快速查找是否已经存在一个与当前节点的值之和等于目标值的节点。

步骤：

1. 中序遍历：对二叉搜索树进行中序遍历，访问每个节点。
2. 哈希集合：对于每个节点的值 x，判断目标值 k - x 是否已经存在于哈希集合中。如果存在，则说明找到了符合条件的两个节点。
3. 插入当前节点值：如果当前节点值不满足条件，将其插入哈希集合中，以便后续节点检查。

代码实现：

pythonCopy Code
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        # 用于存储遍历到的节点值
        seen = set()

        # 定义中序遍历函数
        def inorder(node):
            if not node:
                return False
            # 左子树递归
            if inorder(node.left):
                return True
            # 如果差值 (k - node.val) 已经在seen中，说明找到了
            if k - node.val in seen:
                return True
            # 将当前节点值加入集合
            seen.add(node.val)
            # 右子树递归
            return inorder(node.right)

        # 从根节点开始遍历
        return inorder(root)

代码解析：

1. seen 集合用于存储已访问的节点值。
2. inorder 函数是一个递归函数，它对二叉树进行中序遍历。
3. 每次访问一个节点时，检查 k - node.val 是否已经在 seen 中。如果在，说明已经找到两个值的和为 k，直接返回 True。
4. 如果当前节点值不满足条件，就将其加入 seen 集合，继续遍历。

时间复杂度：

• 中序遍历二叉树的时间复杂度是 O(n)，其中 n 是节点的数量。
• 对每个节点，插入和查找哈希集合的时间复杂度为 O(1)。 因此，整体的时间复杂度是 O(n)。

空间复杂度：

• 哈希集合的空间复杂度为 O(n)，最坏情况下，哈希集合会存储所有节点值。

3. 解法二：双指针法

在二叉搜索树中，我们也可以利用中序遍历获得一个有序的数组，然后使用双指针法来查找两个值的和是否为目标值 k。双指针法在有序数组中查找两个数和的经典方法是从两端开始，一个指向数组的起始位置，一个指向末尾，然后根据当前两指针指向的元素值的和与目标值 k 的大小关系来移动指针。

步骤：

1. 中序遍历：对二叉树进行中序遍历，将所有节点值存入一个有序数组。
2. 双指针：在有序数组中，使用两个指针分别指向数组的两端，逐步移动指针，直到找到一对元素和为目标值 k，或者两个指针相遇。

代码实现：

pythonCopy Code
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        # 中序遍历结果数组
        inorder_values = []

        # 定义中序遍历函数
        def inorder(node):
            if node:
                inorder(node.left)
                inorder_values.append(node.val)
                inorder(node.right)

        # 获取中序遍历结果
        inorder(root)

        # 使用双指针查找是否有两个数之和为k
        left, right = 0, len(inorder_values) - 1
        while left < right:
            total = inorder_values[left] + inorder_values[right]
            if total == k:
                return True
            elif total < k:
                left += 1
            else:
                right -= 1

        return False

代码解析：

1. inorder_values 列表用于存储中序遍历得到的节点值。
2. inorder 函数递归地遍历树，将节点值存入 inorder_values 列表中。
3. 使用双指针 left 和 right 分别指向 inorder_values 列表的两端，判断它们的和与目标值 k 的关系。
4. 如果当前和小于目标值，则移动左指针；如果当前和大于目标值，则移动右指针。若找到符合条件的节点对，则返回 True。

时间复杂度：

• 中序遍历二叉树的时间复杂度是 O(n)，其中 n 是节点的数量。
• 双指针法的时间复杂度是 O(n)，因为我们最多遍历一次数组。 因此，整体时间复杂度为 O(n)。

空间复杂度：

• 存储中序遍历结果的数组需要 O(n) 的空间。

实际应用场景

1. 数据库查询优化

在数据库中，通常会有一个索引结构，类似于二叉搜索树，用于加速数据的检索。当我们需要查找满足某个条件的两条记录时，例如两个记录的值之和等于某个目标值，可以将二叉搜索树和查找算法结合起来，通过优化查找速度，来提高数据库查询的效率。

例如，假设我们有一个二叉搜索树，它存储了某个商品的价格信息，我们需要查找是否有两个商品的价格之和等于某个指定的金额。如果使用传统的暴力算法，我们需要遍历所有的商品进行比较，而使用二叉搜索树和上述的查找算法，我们可以大大减少查找的次数，从而提高查询效率。

2. 图像处理中的匹配问题

在图像处理领域，特别是图像匹配和特征匹配中，很多时候需要比较不同图像的特征点之间的相似度。例如，假设我们有两组特征点，分别存储在两个二叉搜索树中，并且我们需要查找是否存在两个特征点的匹配值。通过将这些特征点值插入到二叉搜索树中，我们可以快速找到符合条件的特征点对。

3. 数字货币交易

在数字货币交易平台中，用户的买卖请求通常会存储在一个二叉搜索树中，其中每个节点代表一个买单或卖单。当用户发起一个新的交易请求时，平台需要检查是否有现有的交易请求可以与其匹配。通过使用二叉搜索树，平台可以在较短的时间内找到符合条件的交易对。

总结

本题的关键在于二叉搜索树的结构特性以及如何利用这些特性优化查找过程。通过中序遍历和哈希集合或双指针等方法，我们能够高效地解决这个问题。无论是从时间复杂度还是空间复杂度的角度考虑，解法都表现得非常优秀，能够处理大规模的数据集。在实际应用中，这种技巧也能够有效地提升算法的性能，特别是在涉及到大量数据查找和优化的场景中。