Skip to content

Commit 040066f

Browse files
fishercoder1534fishercoder1534
committed
add 1214
1 parent 290d0dc commit 040066f

File tree

3 files changed

+133
-0
lines changed

3 files changed

+133
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,6 +56,7 @@ _If you like this project, please leave me a star._ ★
5656
|1228|[Missing Number In Arithmetic Progression](https://leetcode.com/problems/missing-number-in-arithmetic-progression/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1228.java) | |Easy||
5757
|1221|[Split a String in Balanced Strings](https://leetcode.com/problems/split-a-string-in-balanced-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1221.java) | |Easy|Greedy|
5858
|1217|[Play with Chips](https://leetcode.com/problems/play-with-chips/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1217.java) | |Easy|Array, Math, Greedy|
59+
|1214|[Two Sum BSTs](https://leetcode.com/problems/two-sum-bsts/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1214.java) | |Medium| Binary Search Tree|
5960
|1213|[Intersection of Three Sorted Arrays](https://leetcode.com/problems/intersection-of-three-sorted-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1213.java) | [:tv:](https://www.youtube.com/watch?v=zceoOrHSHNQ)|Easy||
6061
|1207|[Unique Number of Occurrences](https://leetcode.com/problems/unique-number-of-occurrences/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1207.java) | [:tv:](https://www.youtube.com/watch?v=_NYimlZY1PE)|Easy||
6162
|1200|[Minimum Absolute Difference](https://leetcode.com/problems/minimum-absolute-difference/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1200.java) | [:tv:](https://www.youtube.com/watch?v=mH1aEjOEjcQ)|Easy||

‎src/main/java/com/fishercoder/solutions/_1214.java

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
8+
/**
9+
* 1214. Two Sum BSTs
10+
*
11+
* Given two binary search trees,
12+
* 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.
13+
*
14+
* Example 1:
15+
* 2 1
16+
* / \ / \
17+
* 1 4 0 3
18+
*
19+
* Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
20+
* Output: true
21+
* Explanation: 2 and 3 sum up to 5.
22+
*
23+
* Example 2:
24+
* 0 5
25+
* / \ / \
26+
* -10 10 1 7
27+
* / \
28+
* 0 2
29+
*
30+
* Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
31+
* Output: false
32+
*
33+
* Constraints:
34+
* Each tree has at most 5000 nodes.
35+
* -10^9 <= target, node.val <= 10^9
36+
* */
37+
public class _1214 {
38+
public static class Solution1 {
39+
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
40+
if (root1 == null || root2 == null) {
41+
return false;
42+
}
43+
List<Integer> inorder1 = inorderDfs(root1, new ArrayList<>());
44+
List<Integer> inorder2 = inorderDfs(root2, new ArrayList<>());
45+
return findTwoSum(inorder1, inorder2, target);
46+
}
47+
48+
private boolean findTwoSum(List<Integer> sorted1, List<Integer> sorted2, int target) {
49+
for (int i = 0; i < sorted1.size(); i++) {
50+
if (exists(sorted2, target - sorted1.get(i))) {
51+
return true;
52+
}
53+
}
54+
return false;
55+
}
56+
57+
private boolean exists(List<Integer> sorted, int target) {
58+
int left = 0;
59+
int right = sorted.size() - 1;
60+
while (left <= right) {
61+
int mid = left + (right - left) / 2;
62+
if (sorted.get(mid) == target) {
63+
return true;
64+
} else if (sorted.get(mid) < target) {
65+
left = mid + 1;
66+
} else {
67+
right = mid - 1;
68+
}
69+
}
70+
return false;
71+
}
72+
73+
private List<Integer> inorderDfs(TreeNode root, List<Integer> list) {
74+
if (root == null) {
75+
return list;
76+
}
77+
if (root.left != null) {
78+
list = inorderDfs(root.left, list);
79+
}
80+
list.add(root.val);
81+
if (root.right != null) {
82+
list = inorderDfs(root.right, list);
83+
}
84+
return list;
85+
}
86+
87+
}
88+
}

‎src/test/java/com/fishercoder/_1214Test.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions._1214;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import java.util.Arrays;
10+
11+
import static org.junit.Assert.assertEquals;
12+
13+
public class _1214Test {
14+
private static _1214.Solution1 solution1;
15+
private static TreeNode root1;
16+
private static TreeNode root2;
17+
18+
@BeforeClass
19+
public static void setup() {
20+
solution1 = new _1214.Solution1();
21+
}
22+
23+
@Test
24+
public void test1() {
25+
root1 = TreeUtils.constructBinaryTree(Arrays.asList(2, 1, 4));
26+
root2 = TreeUtils.constructBinaryTree(Arrays.asList(1, 0, 3));
27+
assertEquals(true, solution1.twoSumBSTs(root1, root2, 5));
28+
}
29+
30+
@Test
31+
public void test2() {
32+
root1 = TreeUtils.constructBinaryTree(Arrays.asList(0, -10, 10));
33+
root2 = TreeUtils.constructBinaryTree(Arrays.asList(5, 1, 7, 0, 2));
34+
assertEquals(false, solution1.twoSumBSTs(root1, root2, 18));
35+
}
36+
37+
@Test
38+
public void test3() {
39+
root1 = TreeUtils.constructBinaryTree(Arrays.asList(0, -10, 10));
40+
root2 = TreeUtils.constructBinaryTree(Arrays.asList(5, 1, 7, 0, 2));
41+
assertEquals(true, solution1.twoSumBSTs(root1, root2, 17));
42+
}
43+
44+
}

0 commit comments

Comments
 (0)