题目大意：
查找两棵二叉搜索树之和
给出两棵二叉搜索树，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值 Target。
如果可以找到返回 True，否则返回 False。
示例1：
输入：root1 = [2,1,4], root2 = [1,0,3], target = 5 输出：true 解释：2 加 3 和为 5 。
示例2：
输入：root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18 输出：false
提示：
- 每棵树上最多有 5000 个节点。
- -10^9 <= target, node.val <= 10^9
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1214
解题思路分析：
这是一道二叉搜索树版本的Two Sum，二叉搜索树的基本特征即是，当前节点的左侧子分支都小于自身，而右侧子分支都大于自身。我们可以遍历一棵树A的所有节点，分别用这些节点去另外一棵树B去寻找和，如果A树与B树当前节点和等于target，返回true，不相同时，进行二分查找：若大于target时，B树的节点移动到其左子节点，小于target时移动到B的右子节点。当B树遍历结束之后仍没找到答案，此时可将A树的当前节点移动到其左子节点或右子节点，然后再在B树中二分查找。
实现代码：
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
// 如果root2为空，返回false
if(root2==null) return false;
// 利用root2的当前节点去root1中找到和为target的值。
// 若没找到，继续用root2的左右子节点去找
return help(root1, root2.val, target)
|| twoSumBSTs(root1, root2.left, target)
|| twoSumBSTs(root1, root2.right, target);
}
boolean help(TreeNode root1, int value, int target){
// 如果root1为空返回false
if(root1==null) return false;
// 计算两棵树当前节点和
int sum=root1.val+value;
// 如果sum等于target，返回true
if(sum==target) return true;
// 如果sum大于target，减小root1的值
if(sum>target){
// 使用root1左子节点的值继续递归
return help(root1.left,value,target);
}else{ // 反之
// 使用root1右子节点的值继续递归
return help(root1.right,value,target);
}
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Two Sum BSTs.
Memory Usage: 39.5 MB, less than 100.00% of Java online submissions for Two Sum BSTs.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1214-two-sum-bsts-解题思路分析/