题目描述
给出两棵二叉搜索树,请你从两棵树中各找出一个节点,使得这两个节点的值之和等于目标值 Target
。
如果可以找到返回 True
,否则返回 False
。
样例
输入:root1 = [2,1,4], root2 = [1,0,3], target = 5
输出:true
解释:2 加 3 和为 5 。
输入:root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
输出:false
限制
- 每棵树上最多有
5000
个节点。 -10^9 <= target, node.val <= 10^9
算法
(枚举 + 哈希表) $O(n + m)$
- 以任何方式遍历第一棵树,将所有结点的值放入到非空集合
unordered_set
中。 - 然后遍历第二棵树,判断
target - r -> val
是否存在于集合中,如果存在,直接返回true
。
时间复杂度
- 每个结点最多遍历一次,且集合的插入和查询复杂度都是常数,故时间复杂度为 $O(n + m)$。
空间复杂度
- 需要额外的空间存放集合。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void traverse1(TreeNode *r, unordered_set<int>& v) {
if (!r)
return;
v.insert(r -> val);
traverse1(r -> left, v);
traverse1(r -> right, v);
}
bool traverse2(TreeNode *r, const unordered_set<int>& v, int target) {
if (!r)
return false;
if (v.find(target - r -> val) != v.end())
return true;
if (traverse2(r -> left, v, target))
return true;
if (traverse2(r -> right, v, target))
return true;
return false;
}
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
unordered_set<int> v;
traverse1(root1, v);
return traverse2(root2, v, target);
}
};