难度: Easy
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
示例 1：
输入: root = [8,6,10,5,7,9,11], k = 12 输出: true 解释: 节点 5 和节点 7 之和等于 12
示例 2：
输入: root = [8,6,10,5,7,9,11], k = 22 输出: false 解释: 不存在两个节点值之和为 22 的节点
提示：
[1, 104].-104 <= Node.val <= 104root 为二叉搜索树-105 <= k <= 105注意：本题与主站 653 题相同： https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
运行时间: 40 ms
内存: 18.9 MB
class Solution:
def __init__(self):
self.s = set()
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
if root is None:
return False
if k - root.val in self.s:
return True
self.s.add(root.val)
return self.findTarget(root.left, k) or self.findTarget(root.right, k)
这个题解采用了递归的深度优先搜索方法结合哈希表来查找是否存在两个节点值的和等于 k。每次访问一个节点时，首先检查哈希表中是否存在一个值等于 k - 当前节点值，如果存在则返回 true，表示找到了这样的两个节点。如果不存在，则将当前节点的值添加到哈希表中，并递归地继续检查左右子节点。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def __init__(self):
self.s = set() # 初始化一个空的哈希集合
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
if root is None: # 如果节点为空，直接返回 False
return False
if k - root.val in self.s: # 检查 k - 当前节点值是否在哈希集中
return True # 如果存在，说明找到了两个节点的和为 k
self.s.add(root.val) # 将当前节点值添加到哈希集中
# 递归检查左子树和右子树
return self.findTarget(root.left, k) or self.findTarget(root.right, k)
选择递归深度优先搜索配合哈希表的方法可以有效地在遍历树的同时检查和更新节点值与目标值k的关系。这种方法的优势在于即时更新查找表（哈希表），并在O(1)的时间复杂度内完成查找操作，从而保持整体算法的效率。另外，使用哈希表可以快速检查是否存在某个特定的补数（k - 当前节点值）。除此之外，还有其他方法，例如使用两个指针在中序遍历得到的有序数组上进行操作，类似于解决有序数组的两数之和问题。但这需要额外的空间来存储中序遍历的结果，并且相对复杂。
在递归过程中，每次访问一个节点时都会将节点值添加到哈希表中，哈希表自身具有防止元素重复的特性（即同一个值不会被添加两次）。因此，通过将访问过的节点值存入哈希表，可以确保每个节点值只被计算一次，避免了重复计算。
如果两个节点的值分别位于二叉搜索树的两端，递归方法仍然能够有效地找到这两个节点。由于算法是通过深度优先搜索实现的，它会完整地遍历树的所有节点，直到找到符合条件的节点为止。虽然在最坏的情况下可能需要遍历树的所有节点，使得时间复杂度为O(n)，但这仍然是相对高效的，因为每个节点只被访问一次。总的来说，即使节点值位于树的两端，算法的效率也主要取决于树的结构和节点的总数。