Given the roots of two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.
Example 1:
Input: root1 = [2,1,4], root2 = [1,0,3], target = 5 Output: true Explanation: 2 and 3 sum up to 5.
Example 2:
Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18 Output: false
Constraints:
- The number of nodes in each tree is in the range
[1, 5000]. -109 <= Node.val, target <= 109
查找两棵二叉搜索树之和。
给出两棵二叉搜索树，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值
Target。如果可以找到返回True，否则返回False。提示：
每棵树上最多有 5000 个节点。
-10^9 <= target, node.val <= 10^9来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-bsts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题我给出两种思路。一是利用hashset，二是利用BST的中序遍历。
hashset 的做法是，我们为这两棵树各自创建一个 hashset 来记录这两棵树里面的节点值。记录好以后，我们遍历其中一个 hashset 的值 val，并在另一个 hashset 里找是否存在 target - val，如果存在则 return true。
时间O(n)
空间O(n)
Java实现
1 /**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode() {}
8 * TreeNode(int val) { this.val = val; }
9 * TreeNode(int val, TreeNode left, TreeNode right) {
10 * this.val = val;
11 * this.left = left;
12 * this.right = right;
13 * }
14 * }
15 */
16 class Solution {
17 public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
18 HashSet<Integer> set1 = new HashSet<>();
19 HashSet<Integer> set2 = new HashSet<>();
20 helper(root1, set1);
21 helper(root2, set2);
22 for (int num : set1) {
23 if (set2.contains(target - num)) {
24 return true;
25 }
26 }
27 return false;
28 }
29
30 private void helper(TreeNode root, HashSet<Integer> set) {
31 if (root == null) {
32 return;
33 }
34 set.add(root.val);
35 helper(root.left, set);
36 helper(root.right, set);
37 }
38 }
BST 的中序遍历的做法是，我们为这两棵树各自创建一个 stack，我们暂且记为 stack1 和 stack2。对于 root1，我们做中序遍历，一开始不停地把左子树加入 stack1；对于 root2，我们做逆向的中序遍历，一开始不停地把右子树加入 stack2。因为 BST 在做中序遍历的时候结果是有序的，所以 root1 的遍历结果是递增的，root2 的遍历结果是递减的。如果 root1.val + root2.val < target 则需要再找 root1 中序遍历的下一个节点，因为他会使得 root1.val + root2.val 更大；反之则需要再找 root2 逆向中序遍历的下一个节点，因为他会使得 root1.val + root2.val 更小。
时间O(n)
空间O(n)
Java实现
1 /**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode() {}
8 * TreeNode(int val) { this.val = val; }
9 * TreeNode(int val, TreeNode left, TreeNode right) {
10 * this.val = val;
11 * this.left = left;
12 * this.right = right;
13 * }
14 * }
15 */
16 class Solution {
17 public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
18 // corner case
19 if (root1 == null || root2 == null) {
20 return false;
21 }
22
23 // normal case
24 Deque<TreeNode> stack1 = new ArrayDeque<>();
25 Deque<TreeNode> stack2 = new ArrayDeque<>();
26 TreeNode t1;
27 TreeNode t2;
28 while (true) {
29 while (root1 != null) {
30 stack1.push(root1);
31 root1 = root1.left;
32 }
33 while (root2 != null) {
34 stack2.push(root2);
35 root2 = root2.right;
36 }
37 if (stack1.isEmpty() || stack2.isEmpty()) {
38 break;
39 }
40
41 t1 = stack1.peek();
42 t2 = stack2.peek();
43 if (t1.val + t2.val == target) {
44 return true;
45 }
46 // inorder traversal for root1
47 else if (t1.val + t2.val < target) {
48 stack1.pop();
49 root1 = t1.right;
50 }
51 // inorder traversal for root2
52 else {
53 stack2.pop();
54 root2 = t2.left;
55 }
56 }
57 return false;
58 }
59 }