LeetCode 1214. 查找两棵二叉搜索树之和
目录
题目描述
题意分析
要的只是一个布尔值：能不能从第一棵树里挑一个节点、从第二棵树里挑一个节点，让两者的值相加等于 target。不需要返回具体是哪两个节点，也不需要统计有多少对。
「一棵一个」这个限制很重要——它排除了同一棵树内部两两配对的情况，所以两棵树可以被完全区别对待：一棵负责提供候选值，另一棵负责发起查询。
输入被声明为二叉搜索树，这透露出两条可用信号：一是节点值在树内互不重复且中序有序，二是从根往下比较可以在 $O(h)$ 内定位一个值。但这两条都是「可以用」而非「必须用」，因为题目只要求存在性判断，不要求利用有序性把复杂度压到线性以下。
边界：任一棵树为空、target 恰好等于某个节点值的两倍（但两个节点必须来自不同的树，所以这不构成自配对问题）、节点值为负数、两棵树规模悬殊。
解法：哈希集合 + DFS
核心思路
暴力做法是对第一棵树的每个节点都完整扫描第二棵树，复杂度 $O(nm)$。重复工作在于：第二棵树一遍遍回答同一种问题——「是否存在给定值」。
用哈希集合预处理其中一棵树即可消除重复扫描。代码先把
root1的所有节点值放入集合，再遍历root2；访问值v时，只需查询集合中是否存在target - v。两个值天然来自不同的树，因此不需要像单树两数之和那样排除同一节点。
查询阶段的不变量是：开始遍历
root2之前，集合恰好包含root1的全部值；因此对任一已访问节点v，set.contains(target - v)当且仅当存在一个来自root1的节点与它配对。命中时立即返回true；若遍历完root2仍未命中，则所有跨树数对都已被覆盖，答案只能是false。
这里选择哈希法是因为它最容易在面试中一次写对，期望时间 $O(n+m)$。它没有利用 BST 的有序性；若内存更紧，可以用两个方向相反的中序迭代器做双指针，把额外空间降到 $O(h_1+h_2)$，但实现更长。对另一棵 BST 逐点查补数只在树平衡时是 $O(n\log m)$，退化链表时会变成 $O(nm)$，不如哈希法稳定。
解题步骤
- 先把第一棵树的所有节点值收进
Set<Long>。遍历顺序不影响集合内容，前序写法最直接；使用long计算补数，避免target - node.val在更宽输入范围下发生 32 位溢出。
- 递归的空节点分支直接
return，不做任何事。为什么必须写在最前：BST 的叶子节点的左右孩子都是 null，不拦住就会立刻空指针。
- 遍历第二棵树，每到一个节点先查
set.contains((long) target - node.val)；命中就立即返回true，不再访问剩余子树。
- 未命中就递归左右子树，用
||合并结果。为什么用||而不是先算两边再取或：Java 和 Go 的||都是短路求值，左子树一旦返回 true，右子树整棵都不会被访问，这就是天然的提前退出。
- 第二棵树的空节点分支返回
false，它是||的中性值。任一输入树为空时，流程也会自然返回false，无需额外特判。
以
root1 = [2,1,4]、root2 = [1,0,3]、target = 5为例：先得到集合{2,1,4}。访问root2的根节点 1 时查询补数 4，立即命中并返回true，左右子树无需访问。若把target改成 9，依次查询补数 8、9、6 都不命中，完整遍历root2后返回false。
代码实现
import java.util.HashSet;
import java.util.Set;
// 先把树1的值全收进集合，再遍历树2逐点查补值。
class Solution {
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
Set<Long> set = new HashSet<>();
collect(root1, set);
return exists(root2, set, target);
}
private void collect(TreeNode node, Set<Long> set) {
if (node == null) {
return;
}
set.add((long) node.val);
collect(node.left, set);
collect(node.right, set);
}
private boolean exists(TreeNode node, Set<Long> set, int target) {
if (node == null) {
return false;
}
if (set.contains((long) target - node.val)) {
return true;
}
return exists(node.left, set, target) || exists(node.right, set, target);
}
}
// 先把树1的值全收进集合，再遍历树2逐点查补值。
func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
set := make(map[int64]struct{})
collect(root1, set)
return exists(root2, set, target)
}
func collect(node *TreeNode, set map[int64]struct{}) {
if node == nil {
return
}
set[int64(node.Val)] = struct{}{}
collect(node.Left, set)
collect(node.Right, set)
}
func exists(node *TreeNode, set map[int64]struct{}, target int) bool {
if node == nil {
return false
}
if _, ok := set[int64(target)-int64(node.Val)]; ok {
return true
}
return exists(node.Left, set, target) || exists(node.Right, set, target)
}
复杂度分析
- 时间复杂度：期望为 $O(n + m)$，其中 $n$、$m$ 分别是两棵树的节点数。每个节点最多访问一次，哈希插入和查询的期望成本为 $O(1)$。
- 空间复杂度：$O(n + \max(h_1,h_2))$。集合保存第一棵树的 $n$ 个值；两次 DFS 顺序执行，调用栈不会同时存在，所以峰值取两棵树高度的较大值。退化链表下最坏为 $O(n+m)$。
关键点总结
- 两个独立集合各取一个元素凑目标值时，可以固定一边建哈希集合，遍历另一边查补数，把笛卡尔积降成两次线性遍历。
- BST 有序性不是必须使用的条件。哈希法优先保证实现短且期望线性；若空间限制严格，再用双中序迭代器把集合空间降为树高空间。
- 收集 DFS 负责建立完整集合；查询 DFS 的布尔返回值表示「当前子树是否存在补数」，两个阶段的职责和不变量要分开。
- 用
||的短路特性做提前退出，是树上存在性搜索的免费剪枝，不需要额外写 flag。
- 补数运算先转为 64 位，避免先在 32 位中溢出后再装箱；类型提升必须发生在减法之前。
易错点总结
- 错误写法：
collect里不判node == null就访问node.val→ 以root1 = [2,1,4]为例，递归到叶子 1 的左孩子时立刻抛出空指针异常。
- 错误写法：把两棵树的值都塞进同一个集合再找配对 →
root1 = [2]、root2 = [5]、target = 4时，集合是{2, 5}，2 和自己配对被判成 true，但题目要求两个节点来自不同的树，正确答案是 false。
- 错误写法：
exists的空节点分支返回 true →root2 = [1]、target = 100时，根节点未命中后递归到 null 孩子返回 true，整体错误地返回 true。
- 错误写法：查询时写成
set.contains(node.val - target)→ 把减法方向搞反，target = 5、节点值 1 时查的是 -4 而不是 4，示例直接漏解返回 false。
- 错误写法：仅凭
node.val > target就剪掉root2的右子树。root1 = [-30]、root2 = [8,3,20]、target = -10时，根节点 8 大于目标却不能剪枝，因为右侧的 20 与 -30 正好配对。
- 错误写法：只遍历第二棵树的左子树。
root1 = [5]、root2 = [1,0,3]、target = 8的唯一配对来自右子树节点 3，会被漏掉。
- 错误写法：先用 32 位
int做target - node.val，再把结果转成long。一旦输入范围扩展到使差值越界，转换已经来不及；应先提升操作数再相减。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1. 两数之和 | 简单 | 单数组内边查边存，必须处理自己和自己配对 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 已排序，用相向双指针把空间压到 $O(1)$ |
| 653. 两数之和 IV - 输入二叉搜索树 | 简单 | 同一棵 BST 内配对，需排除节点与自身相加 |
| 1099. 小于 K 的两数之和 | 简单 | 条件从相等变成小于，哈希失效必须转排序双指针 |