LeetCode 653. Two Sum IV - Input is a BST 题解
LeetCode 653. Two Sum IV - Input is a BST 题解
题目描述
给定一个二叉搜索树root和一个目标结果k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回true。
示例 1：
输入: root = [5,3,6,2,4,null,7], k = 9 输出: true示例 2：
输入: root = [5,3,6,2,4,null,7], k = 28 输出: false解题思路
方法一：中序遍历 + 双指针
思路：
- 对二叉搜索树进行中序遍历，得到一个递增的序列
- 使用双指针在递增序列中查找两个数之和等于目标值
复杂度分析：
- 时间复杂度：O(n)，其中 n 是二叉搜索树的节点个数。需要遍历二叉树一次，然后使用双指针遍历序列一次。
- 空间复杂度：O(n)，需要使用栈来进行中序遍历，以及存储遍历结果。
方法二：哈希表
思路：
- 使用哈希表来存储已经访问过的节点值
- 遍历二叉搜索树，对于每个节点，检查
k - node.val是否在哈希表中 - 如果在，返回
true；否则，将当前节点值加入哈希表
复杂度分析：
- 时间复杂度：O(n)，其中 n 是二叉搜索树的节点个数。每个节点只被访问一次。
- 空间复杂度：O(n)，需要使用哈希表来存储已访问的节点值。
代码实现
方法一：中序遍历 + 双指针
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def findTarget(self, root: Optional[TreeNode], k: int) -> bool: # 中序遍历二叉树 def inorder(node): if not node: return [] return inorder(node.left) + [node.val] + inorder(node.right) # 使用双指针在递增序列中查找两个数之和等于目标值 inorder_result = inorder(root) left = 0 right = len(inorder_result) - 1 while left < right: current_sum = inorder_result[left] + inorder_result[right] if current_sum == k: return True elif current_sum < k: left += 1 else: right -= 1 return False方法二：哈希表
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def findTarget(self, root: Optional[TreeNode], k: int) -> bool: seen = set() def dfs(node): if not node: return False if k - node.val in seen: return True seen.add(node.val) return dfs(node.left) or dfs(node.right) return dfs(root)测试用例
测试用例 1：
输入：root = [5,3,6,2,4,null,7], k = 9
输出：true
测试用例 2：
输入：root = [5,3,6,2,4,null,7], k = 28
输出：false
总结
本题是二叉搜索树的经典问题，主要考察对二叉搜索树性质的理解和应用。通过使用中序遍历 + 双指针或哈希表，我们可以高效地在二叉搜索树中查找两个节点值之和等于目标值。
中序遍历 + 双指针的核心思想是：利用二叉搜索树的中序遍历结果是递增序列的性质，使用双指针在递增序列中查找两个数之和等于目标值。哈希表的核心思想是：遍历二叉搜索树，使用哈希表存储已访问的节点值，检查k - node.val是否在哈希表中。
在实际应用中，哈希表方法通常更受欢迎，因为它只需要遍历二叉树一次，而不需要存储整个遍历结果。
这种方法不仅适用于两数之和 IV 问题，还可以应用于许多其他需要在二叉搜索树中查找元素的场景。掌握这些方法，对于解决这类问题非常重要。