LeetCode LCR 056. 两数之和 IV - 输入二叉搜索树
目录
题目描述
题意分析
题目目标：给定一棵二叉搜索树和整数
k，判断树中是否存在两个不同的节点，使它们的值之和恰好等于k，返回布尔值。
核心约束：只要判定存在性，不必给出具体是哪两个节点，这意味着一旦找到就可以立即返回；"两个不同节点"这条限制说明同一个节点不能用两次，因此配对时必须保证另一半来自别处；节点值互不相同，但值可能为负，k也可能为负。
边界处理：只有一个节点时永远返回假；k恰好是某节点值的两倍时不能把该节点自己配给自己；节点值加起来可能超出单个值的范围，但题目量级下 32 位整型足够。
实现取舍：判定"某个具体的数是否出现过"是一个纯粹的查找问题，与树的形状无关；只要能在遍历中随时回答"我需要的那一半见过没有"，一趟遍历就够了。
解法：滑动窗口维护区间
核心思路
暴力做法是枚举两个节点再判断和是否为
k，代价 $O(n^2)$；稍好一点的是对每个节点在树里查找k - val，代价 $O(n \log n)$，但要小心查到的正是自己。
换个角度：配对问题的本质是"对当前元素x，是否存在另一元素等于k - x"。把已经访问过的节点值放进一张集合表里，遍历到某个节点时先查表——命中就说明存在一个先前访问过的、必然与当前节点不同的节点与它配对成功，直接返回真。
由此确定不变量：进入节点x并完成查表之前，集合中恰好装着遍历序中排在x之前的所有节点值，不含x自己。正是"不含自己"这一点，让"两个节点必须不同"这条限制自动被满足，不需要任何额外判断。
查表未命中就把当前值加入集合，再递归左右子树；只要任意一侧返回真就整体返回真，短路求值让答案一旦确定就不再继续搜索。注意这个思路完全没有用到二叉搜索树的有序性——它对任意二叉树都成立，这既是它的通用之处，也是面试时值得主动点破的一点。
解题步骤
- 主函数初始化一张空集合，然后调用递归。为什么集合要放在递归之外：它承载的是"全局已访问过的值"，若每层递归各持一份，跨子树的配对就找不到了。
- 递归入口遇到空节点返回假。为什么返回假：空子树不含任何节点，既不能提供配对也不能声明成功，返回假让上层的短路逻辑继续往别处找。
- 先执行
if (nodes.contains(k - root.val)) return true;。为什么查表要在插入之前：若先插入自己，当k恰好等于当前值的两倍时会查到自己，把一个节点当成两个用，判定就错了。- 查表失败后执行
nodes.add(root.val)。为什么此时才插入：插入之后当前值才对后续节点可见，这正好维持了"集合中只含遍历序在前者"的不变量。- 返回
find(root.left, k) || find(root.right, k)。为什么用短路或：左子树一旦找到答案就无需再搜右子树，能显著减少无效访问；同时两侧共享同一张集合，跨子树的配对也能被发现。- 以
具体用例：树[5, 3, 6, 2, 4, null, 7]，k = 9走一遍。访问 5：查9 - 5 = 4，集合为空未命中，插入 5。访问 3：查9 - 3 = 6，集合{5}未命中，插入 3。访问 2：查 7，未命中，插入 2。访问 4：查9 - 4 = 5，集合{5, 3, 2}命中，立即返回真，对应节点对(4, 5)，二者确实是不同节点。再看反例，同一棵树取k = 10：一路访问下来集合逐渐变成{5, 3, 2, 4, 6}，访问 7 时查10 - 7 = 3命中，返回真，对应(3, 7)。最后看一个必须靠"先查后插"才正确的用例，树[1, null, 2]且k = 2：访问 1 时查2 - 1 = 1，集合为空未命中，随后才插入 1，避免了把 1 与自己配对；访问 2 时查 0 未命中，最终返回假，正确。
代码实现
// 核心实现：滑动窗口维护区间，维护必要状态并避免重复处理。
class Solution {
private Set<Integer> nodes;
public boolean findTarget(TreeNode root, int k) {
nodes = new HashSet<>();
return find(root, k);
}
private boolean find(TreeNode root, int k) {
if (root == null) {
return false;
}
if (nodes.contains(k - root.val)) {
return true;
}
nodes.add(root.val);
return find(root.left, k) || find(root.right, k);
}
}
// 核心实现：滑动窗口维护区间，维护必要状态并避免重复处理。
func findTarget(root *TreeNode, k int) bool {
nodes := make(map[int]bool)
var find func(root *TreeNode, k int) bool
find = func(root *TreeNode, k int) bool {
if root == nil {
return false
}
if nodes[k-root.Val] {
return true
}
nodes[root.Val] = true
return find(root.Left, k) || find(root.Right, k)
}
return find(root, k)
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：每个节点至多被访问一次，访问时只做一次哈希查询和一次哈希插入，均为常数；命中即返回还能提前结束。
- 空间复杂度：$O(n)$。凭什么：集合最坏要装下几乎所有节点值，加上 $O(h)$ 的递归栈，主项是集合的大小。
关键点总结
- "两数之和"类问题的统一解法是把配对转成查表：遍历到一个元素时问"我的互补数出现过吗"，一趟遍历即可，无论底层是数组还是树。
- "先查后插"的顺序不是风格问题而是正确性问题，它是保证两个元素互不相同的唯一机制；只要题目出现"两个不同的元素"，就必须检查这一处。
- 集合必须跨整棵树共享，才能捕捉分属不同子树的配对；把状态提到递归之外是这类题的通用做法。
- 短路或让答案一旦确定就停止搜索，写
a() || b()而不是先算两个再取或，是判定型递归的标准写法。- 面试视角：这题的加分点在于主动指出"哈希解法没有用到二叉搜索树的性质"，然后给出利用有序性的替代方案——先中序遍历得到升序数组再用左右双指针，时间同样 $O(n)$ 但空间可以讨论；或者对每个节点在树中二分查找互补值，$O(n \log n)$ 时间、$O(h)$ 空间。能说清三种方案在时间与空间上的取舍，简单题也能答出层次。
易错点总结
- 错误写法：先
nodes.add(root.val)再查k - root.val→ 树[1]且k = 2时节点 1 与自己配对，返回真而正确答案是假。- 错误写法：把集合声明在递归函数内部 → 每层递归各持一份空集合，树
[2, 1, 3]且k = 4时 1 与 3 分属不同子树，永远配不上，返回假。- 错误写法：返回
find(left) | find(right)用非短路或 → 结果虽正确但左侧已找到答案时仍会遍历整棵右子树，白白多做工作。- 错误写法：忘记把两个子树的结果并起来，只写
return find(root.left, k);→ 树[5, 3, 6]且k = 11时右子树的 6 从未被访问，返回假。- 错误写法：空节点返回真 → 任何输入都在第一次触底时返回真，树
[1]且k = 100也返回真。- 错误写法：用列表代替集合并线性查找 → 语义正确但每次查找 $O(n)$，整体退化成 $O(n^2)$，大树上超时。
- 错误写法：先中序摊平成数组再用双指针，却在两指针相遇时仍判定成功 → 树
[1]且k = 2时左右指针指向同一元素，返回真，同样违反"两个不同节点"。- 错误写法：改成对每个节点在树中查找
k - val却没有排除查到自身 →k为某节点值两倍时返回真，例如树[2, 1, 3]且k = 4会因为找到 2 自己而误判。- 错误写法：假设节点值非负，用"当前值已大于
k就剪枝"跳过子树 → 树[0, -3, 4]且k = 1时-3与 4 的配对被剪掉，返回假。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1. 两数之和 | 简单 | 数组版原型，需返回下标因此表里存的是位置 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 输入已有序，可用双指针把空间降到常数 |
| 454. 四数相加 II | 中等 | 四数组配对，需把前两组的和预先建表再查后两组 |
| LCR 053. 二叉搜索树中的中序后继 | 中等 | 真正吃有序性的下行查找，与本题的哈希思路成对照 |
| 560. 和为 K 的子数组 | 中等 | 从配对升级为区间求和，表里存的是前缀和出现次数 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 同样在树上做查询，但依据的是中序名次而非值的配对 |