Skip to content

Commit d6c2e13

Browse files
fishercoder1534fishercoder1534
committed
add 776
1 parent fd64dc2 commit d6c2e13

File tree

3 files changed

+134
-0
lines changed

3 files changed

+134
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ Your ideas/fixes/algorithms are more than welcome!
2323
| # | Title | Solutions | Time | Space | Video | Difficulty | Tag
2424
|-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
2525
|779|[K-th Symbol in Grammar](https://leetcode.com/problems/k-th-symbol-in-grammar/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_779.java) | O(logn) | O(1) | |Medium|
26+
|776|[Split BST](https://leetcode.com/problems/split-bst/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_776.java) | O(n) | O(n) | |Medium| Recursion
2627
|771|[Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_771.java) | O(n) | O(m) | |Easy|
2728
|767|[Reorganize String](https://leetcode.com/problems/reorganize-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_767.java) | O(klogk) k is the number of unique characters in given String| O(k) | |Medium|
2829
|766|[Toeplitz Matrix](https://leetcode.com/problems/toeplitz-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_766.java) | O(m*n) | O(1) | |Easy|

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

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
/**
6+
* 776. Split BST
7+
*
8+
* Given a Binary Search Tree (BST) with root node root, and a target value V,
9+
* split the tree into two subtrees where one subtree has nodes that are all smaller or equal to the target value,
10+
* while the other subtree has all nodes that are greater than the target value.
11+
* It's not necessarily the case that the tree contains a node with value V.
12+
* Additionally, most of the structure of the original tree should remain.
13+
* Formally, for any child C with parent P in the original tree,
14+
* if they are both in the same subtree after the split, then node C should still have the parent P.
15+
* You should output the root TreeNode of both subtrees after splitting, in any order.
16+
17+
Example 1:
18+
19+
Input: root = [4,2,6,1,3,5,7], V = 2
20+
Output: [[2,1],[4,3,6,null,null,5,7]]
21+
22+
Explanation:
23+
Note that root, output[0], and output[1] are TreeNode objects, not arrays.
24+
25+
The given tree [4,2,6,1,3,5,7] is represented by the following diagram:
26+
27+
4
28+
/ \
29+
2 6
30+
/ \ / \
31+
1 3 5 7
32+
33+
while the diagrams for the outputs are:
34+
35+
4
36+
/ \
37+
3 6 and 2
38+
/ \ /
39+
5 7 1
40+
41+
Note:
42+
43+
The size of the BST will not exceed 50.
44+
The BST is always valid and each node's value is different.
45+
*/
46+
47+
public class _776 {
48+
public static class Solution1 {
49+
/** credit: https://discuss.leetcode.com/topic/119481/recursive-java-solution */
50+
public TreeNode[] splitBST(TreeNode root, int V) {
51+
TreeNode small = new TreeNode(0);
52+
TreeNode big = new TreeNode(0);
53+
split(root, V, small, big);
54+
return new TreeNode[] {small.right, big.left};
55+
}
56+
57+
private void split(TreeNode root, int v, TreeNode small, TreeNode big) {
58+
if (root == null) {
59+
return;
60+
}
61+
if (root.val <= v) {
62+
small.right = root;
63+
TreeNode right = root.right;
64+
root.right = null;
65+
split(right, v, root, big);
66+
} else {
67+
big.left = root;
68+
TreeNode left = root.left;
69+
root.left = null;
70+
split(left, v, small, root);
71+
}
72+
}
73+
}
74+
75+
public static class Solution2 {
76+
/** credit: https://leetcode.com/articles/split-bst/ */
77+
public TreeNode[] splitBST(TreeNode root, int V) {
78+
if (root == null) {
79+
return new TreeNode[] {null, null};
80+
} else if (root.val <= V) {
81+
TreeNode[] result = splitBST(root.right, V);
82+
root.right = result[0];
83+
result[0] = root;
84+
return result;
85+
} else {
86+
TreeNode[] result = splitBST(root.left, V);
87+
root.left = result[1];
88+
result[1] = root;
89+
return result;
90+
}
91+
}
92+
}
93+
}

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions._776;
6+
import java.util.Arrays;
7+
import org.junit.BeforeClass;
8+
import org.junit.Test;
9+
10+
import static org.junit.Assert.assertArrayEquals;
11+
12+
public class _776Test {
13+
private static _776.Solution1 solution1;
14+
private static _776.Solution2 solution2;
15+
private static TreeNode root;
16+
private static TreeNode small;
17+
private static TreeNode big;
18+
19+
@BeforeClass
20+
public static void setup() {
21+
solution1 = new _776.Solution1();
22+
solution2 = new _776.Solution2();
23+
}
24+
25+
@Test
26+
public void test1() {
27+
root = TreeUtils.constructBinaryTree(Arrays.asList(4, 2, 6, 1, 3, 5, 7));
28+
small = TreeUtils.constructBinaryTree(Arrays.asList(2, 1));
29+
big = TreeUtils.constructBinaryTree(Arrays.asList(4, 3, 6, null, null, 5, 7));
30+
assertArrayEquals(new TreeNode[] {small, big}, solution1.splitBST(root, 2));
31+
}
32+
33+
@Test
34+
public void test2() {
35+
root = TreeUtils.constructBinaryTree(Arrays.asList(4, 2, 6, 1, 3, 5, 7));
36+
small = TreeUtils.constructBinaryTree(Arrays.asList(2, 1));
37+
big = TreeUtils.constructBinaryTree(Arrays.asList(4, 3, 6, null, null, 5, 7));
38+
assertArrayEquals(new TreeNode[] {small, big}, solution2.splitBST(root, 2));
39+
}
40+
}

0 commit comments

Comments
 (0)