您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode Easy653中两数之和输入为BST的示例分析
## 问题描述回顾
LeetCode第653题"Two Sum IV - Input is a BST"题目描述如下：
给定一个二叉搜索树(BST)和一个目标数值`k`，判断BST中是否存在两个节点，其节点值之和等于给定的`k`。
示例1：
输入:
5
/
3 6
/ \
2 4 7
k = 9
输出: true
示例2：
输入:
5
/
3 6
/ \
2 4 7
k = 28
输出: false
## 解题思路分析
### 方法一：哈希表辅助的中序遍历
**核心思想**：利用BST中序遍历的有序性，结合哈希表记录已访问节点值。
```python
def findTarget(root, k):
visited = set()
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
if k - curr.val in visited:
return True
visited.add(curr.val)
curr = curr.right
return False
时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(n)，最坏情况存储所有节点值
实现步骤： 1. 中序遍历得到有序数组 2. 使用双指针在有序数组中查找两数之和
def findTarget(root, k):
nums = []
def inorder(node):
if not node: return
inorder(node.left)
nums.append(node.val)
inorder(node.right)
inorder(root)
left, right = 0, len(nums)-1
while left < right:
total = nums[left] + nums[right]
if total == k:
return True
elif total < k:
left += 1
else:
right -= 1
return False
时间复杂度：O(n)中序遍历 + O(n)双指针 = O(n)
空间复杂度：O(n)存储中序序列
# 用例1：存在解
"""
5
/ \
3 6
/ \ \
2 4 7
"""
root1 = TreeNode(5)
root1.left = TreeNode(3)
root1.right = TreeNode(6)
root1.left.left = TreeNode(2)
root1.left.right = TreeNode(4)
root1.right.right = TreeNode(7)
assert findTarget(root1, 9) == True
# 用例2：无解
assert findTarget(root1, 28) == False
# 用例3：空树
assert findTarget(None, 0) == False
# 用例4：单节点树
root2 = TreeNode(1)
assert findTarget(root2, 1) == False
# 用例5：重复值情况
"""
2
/ \
1 2
"""
root3 = TreeNode(2)
root3.left = TreeNode(1)
root3.right = TreeNode(2)
assert findTarget(root3, 4) == True
利用BST的搜索特性，对每个节点x，在BST中搜索k-x：
def findTarget(root, k):
def search(node, target):
if not node: return False
if node.val == target: return True
return search(node.left, target) if target < node.val else search(node.right, target)
def dfs(node):
if not node: return False
if search(root, k - node.val) and (k - node.val) != node.val:
return True
return dfs(node.left) or dfs(node.right)
return dfs(root)
时间复杂度分析：
最坏情况O(nlogn)（平衡BST）到O(n²)（退化成链表）
适用场景：当BST高度较低时效率较高
// 哈希表法
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
return find(root, k, set);
}
private boolean find(TreeNode node, int k, Set<Integer> set) {
if (node == null) return false;
if (set.contains(k - node.val)) return true;
set.add(node.val);
return find(node.left, k, set) || find(node.right, k, set);
}
// 双指针法
bool findTarget(TreeNode* root, int k) {
vector<int> nums;
inorder(root, nums);
int left = 0, right = nums.size()-1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) return true;
sum < k ? left++ : right--;
}
return false;
}
void inorder(TreeNode* node, vector<int>& nums) {
if (!node) return;
inorder(node->left, nums);
nums.push_back(node->val);
inorder(node->right, nums);
}
# 找出所有可能的解对
def findAllPairs(root, k):
res = []
visited = set()
def traverse(node):
if not node: return
if k - node.val in visited:
res.append([k-node.val, node.val])
visited.add(node.val)
traverse(node.left)
traverse(node.right)
traverse(root)
return res
本文详细分析了LeetCode 653题的多种解法，通过BST的特性优化算法效率。关键要点包括：
最终建议：在面试场景推荐使用哈希表法，因其实现简洁且时间复杂度稳定；在内存敏感环境可考虑双指针法。
本文共计约2150字，通过多种代码示例和详细分析，全面解析了BST中两数之和问题的解决方案。读者可根据实际需求选择适合的算法实现。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。