Skip to content

Commit 7111618

Browse files
xiaoningningxiaoningning
committed
largest bst substree without/with all decendent nodes
1 parent cd8a6c4 commit 7111618

3 files changed

Lines changed: 238 additions & 36 deletions

File tree

‎PuzzleCoding/src/IsBST.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ public static void main(String[] args) {
2424
}
2525

2626
public static boolean isBST(Node node, int min, int max) {
27-
if ((node.left == null) && (node.right == null)){
27+
if ((node == null)){
2828
return true;
2929
}
3030
if ((min < node.value) && (node.value < max)) {
@@ -37,7 +37,7 @@ public static boolean isBST(Node node, int min, int max) {
3737
}
3838

3939
public static boolean isBST1(Node node, int prev) {
40-
if ((node.left == null) && (node.right == null)) {
40+
if ((node == null)) {
4141
return true;
4242
}
4343
if (isBST1(node.left, prev)) {

‎PuzzleCoding/src/LargestBSTSubtree.java‎

Lines changed: 202 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,202 @@
1+
/**
2+
* Given a binary tree,
3+
* find the largest subtree which is a Binary Search Tree (BST),
4+
* where largest means subtree with largest number of nodes in it.
5+
*/
6+
public class LargestBSTSubtree {
7+
8+
public static class LargestBST {
9+
public Node node;
10+
public int maxNode;
11+
public int min;
12+
public int max;
13+
14+
public LargestBST(Node n, int number, int min_value, int max_value) {
15+
node = n;
16+
max = max_value;
17+
min = min_value;
18+
maxNode = number;
19+
}
20+
}
21+
22+
public static void main(String[] args) {
23+
Node root = new Node(10);
24+
Node node5 = new Node(5);
25+
Node node15 = new Node(15);
26+
Node node6 = new Node(6);
27+
Node node7 = new Node(7);
28+
node15.right = node7;
29+
Node node3 = new Node(3);
30+
Node node12 = new Node(12);
31+
Node node11 = new Node(11);
32+
Node node13 = new Node(13);
33+
Node node14 = new Node(14);
34+
35+
root.insert(node5);
36+
root.insert(node6);
37+
root.insert(node15);
38+
root.insert(node3);
39+
root.insert(node12);
40+
root.insert(node11);
41+
root.insert(node13);
42+
root.insert(node14);
43+
44+
int result = largestBSTSubtree(root);
45+
System.out.println(result);
46+
47+
LargestBST largeBST = largestBSTSubtree1(root);
48+
if (largeBST != null)
49+
System.out.println(largeBST.node.value + " : size " + largeBST.maxNode);
50+
51+
LargestBST largeBST2 = largestBSTSubtree2(root);
52+
if (largeBST2 != null)
53+
System.out.println(largeBST2.node.value + " : size " + largeBST2.maxNode);
54+
}
55+
56+
// Given a binary tree, find the largest Binary Search Tree (BST),
57+
// where largest means BST with largest number of nodes in it.
58+
// The largest BST may or may not include all of its descendants.
59+
public static int largestBSTSubtree(Node node) {
60+
if (node == null)
61+
return 0;
62+
if (node.left == null && node.right == null)
63+
return 1;
64+
int leftNode = 0;
65+
int rightNode = 0;
66+
if (node.left != null) {
67+
leftNode = largestBSTSubtree(node.left);
68+
}
69+
if (node.right != null) {
70+
rightNode = largestBSTSubtree(node.right);
71+
}
72+
if (node.left != null && node.right != null) {
73+
if ((node.left.value < node.value) && (node.right.value > node.value)) {
74+
return leftNode + rightNode + 1;
75+
} else if (node.left.value < node.value) {
76+
return leftNode + 1;
77+
} else if (node.right.value > node.value) {
78+
return rightNode + 1;
79+
}
80+
} else if (node.left != null) {
81+
if (node.left.value < node.value)
82+
return leftNode + 1;
83+
else
84+
return leftNode;
85+
} else {// if (node.right != null){
86+
if (node.value < node.right.value)
87+
return rightNode + 1;
88+
else
89+
return rightNode;
90+
}
91+
return Math.max(rightNode, leftNode);
92+
93+
}
94+
95+
// Given a binary tree, find the largest Binary Search Tree (BST),
96+
// where largest means BST with largest number of nodes in it.
97+
// The largest BST may or may not include all of its descendants.
98+
public static LargestBST largestBSTSubtree1(Node node) {
99+
if (node == null)
100+
return null;
101+
if (node.left == null && node.right == null) {
102+
return new LargestBST(node, node.size(), node.value, node.value);
103+
}
104+
105+
LargestBST leftNode = null;
106+
if (node.left != null) {
107+
leftNode = largestBSTSubtree1(node.left);
108+
}
109+
110+
LargestBST rightNode = null;
111+
if (node.right != null) {
112+
rightNode = largestBSTSubtree1(node.right);
113+
}
114+
115+
if (leftNode != null && rightNode != null) {
116+
if ((node.value > leftNode.max && node.left == leftNode.node)
117+
&& (node.value < rightNode.min && node.right == rightNode.node)) {
118+
119+
LargestBST bst = new LargestBST(node,
120+
leftNode.maxNode + rightNode.maxNode + 1,
121+
leftNode.min,
122+
rightNode.max);
123+
124+
return bst;
125+
} else if (node.value > leftNode.max && node.left == leftNode.node) {
126+
return new LargestBST(node, leftNode.maxNode + 1, leftNode.min, node.value);
127+
128+
} else if (node.value < rightNode.min && node.right == rightNode.node) {
129+
return new LargestBST(node, rightNode.maxNode + 1, node.value, rightNode.max);
130+
} else {
131+
return (leftNode.maxNode > rightNode.maxNode) ? leftNode : rightNode;
132+
}
133+
} else if (leftNode != null) {
134+
if (node.value > leftNode.max && node.left == leftNode.node) {
135+
return new LargestBST(node, leftNode.maxNode + 1, leftNode.min, node.value);
136+
} else {
137+
return leftNode;
138+
}
139+
140+
} else if (rightNode != null) {
141+
if (node.value < rightNode.min && node.right == rightNode.node) {
142+
return new LargestBST(node, rightNode.maxNode + 1, node.value, rightNode.max);
143+
} else {
144+
return rightNode;
145+
}
146+
}
147+
148+
return null;
149+
}
150+
151+
// Given a binary tree, find the largest Binary Search Tree (BST),
152+
// where largest means BST with largest number of nodes in it.
153+
// The largest BST must include all of its descendants.
154+
public static LargestBST largestBSTSubtree2(Node node) {
155+
if (node == null)
156+
return null;
157+
if (node.left == null && node.right == null) {
158+
return new LargestBST(node, node.size(), node.value, node.value);
159+
}
160+
161+
LargestBST leftNode = null;
162+
if (node.left != null) {
163+
leftNode = largestBSTSubtree2(node.left);
164+
}
165+
166+
LargestBST rightNode = null;
167+
if (node.right != null) {
168+
rightNode = largestBSTSubtree2(node.right);
169+
}
170+
171+
if (leftNode != null && rightNode != null) {
172+
if ((node.value > leftNode.max && node.left == leftNode.node)
173+
&& (node.value < rightNode.min && node.right == rightNode.node)) {
174+
175+
LargestBST bst = new LargestBST(node,
176+
leftNode.maxNode + rightNode.maxNode + 1,
177+
leftNode.min,
178+
rightNode.max);
179+
180+
return bst;
181+
} else {
182+
return (leftNode.maxNode > rightNode.maxNode) ? leftNode : rightNode;
183+
}
184+
} else if (leftNode != null) {
185+
if (node.value > leftNode.max && node.left == leftNode.node) {
186+
return new LargestBST(node, leftNode.maxNode + 1, leftNode.min, node.value);
187+
} else {
188+
return leftNode;
189+
}
190+
191+
} else if (rightNode != null) {
192+
if (node.value < rightNode.min && node.right == rightNode.node) {
193+
return new LargestBST(node, rightNode.maxNode + 1, node.value, rightNode.max);
194+
} else {
195+
return rightNode;
196+
}
197+
}
198+
return null;
199+
}
200+
201+
202+
}

‎PuzzleCoding/src/LongestBalanceSubstring.java‎

Lines changed: 34 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,27 @@
11
import java.util.HashMap;
22

33
/**
4-
Problem: Given a string which contains only 1 and 0,
5-
find out its longest sub-string that contains equal number of “1” and “0”.
6-
It should be done in O(n) time, O(n) space.
7-
8-
Example: “111100? => 1100, “00110? => 0110, “001111111000? => 111000.
9-
10-
We can use an array index to store the difference
11-
between the number of 1s and the number of 0s up to each character in string S.
12-
That is,we create an array diff with size equals to S.length + 1.
13-
diff[i] is the number of “1”s appeared up to the ith character in S
14-
subtracts the number of “0”s appeared up to ith character in S.
15-
16-
To be more specific, we have this counter initially set to 0,
17-
if we meet a “1”, then counter increases by 1.
18-
Otherwise the counter decreases by 1.
19-
How long is the longest “1 and 0” balanced substring?
20-
That is the longest distance between two identical counter in diff.
21-
Because the counters are the same, they should meet same number of “1”s and “0”s in between.
22-
4+
* Problem: Given a string which contains only 1 and 0,
5+
* find out its longest sub-string that contains equal number of “1” and “0”.
6+
* It should be done in O(n) time, O(n) space.
7+
* <p/>
8+
* Example: “111100? => 1100, “00110? => 0110, “001111111000? => 111000.
9+
* <p/>
10+
* We can use an array index to store the difference
11+
* between the number of 1s and the number of 0s up to each character in string S.
12+
* That is,we create an array diff with size equals to S.length + 1.
13+
* diff[i] is the number of “1”s appeared up to the ith character in S
14+
* subtracts the number of “0”s appeared up to ith character in S.
15+
* <p/>
16+
* To be more specific, we have this counter initially set to 0,
17+
* if we meet a “1”, then counter increases by 1.
18+
* Otherwise the counter decreases by 1.
19+
* How long is the longest “1 and 0” balanced substring?
20+
* That is the longest distance between two identical counter in diff.
21+
* Because the counters are the same, they should meet same number of “1”s and “0”s in between.
2322
*/
2423
public class LongestBalanceSubstring {
25-
public static void main(String[] args){
24+
public static void main(String[] args) {
2625
String s = "1001110010001";
2726
String balanceString = longestBalanceSubstring(s);
2827
System.out.println(balanceString);
@@ -32,27 +31,28 @@ public static void main(String[] args){
3231
System.out.println(balanceString1);
3332

3433
}
35-
public static String longestBalanceSubstring(String s){
36-
if(s.length() <=0)
34+
35+
public static String longestBalanceSubstring(String s) {
36+
if (s.length() <= 0)
3737
return "";
38-
int[] diffCounter = new int[s.length()+1];
38+
int[] diffCounter = new int[s.length() + 1];
3939
diffCounter[0] = 0;
40-
for(int i= 0; i < s.length(); i++){
41-
diffCounter[i+1] = diffCounter[i] + ((s.charAt(i) == '0')? -1:1);
40+
for (int i = 0; i < s.length(); i++) {
41+
diffCounter[i + 1] = diffCounter[i] + ((s.charAt(i) == '0') ? -1 : 1);
4242
}
4343
HashMap<Integer, Integer> counterIndex = new HashMap<Integer, Integer>();
44-
for(int i = 1, j = diffCounter.length-1; i < j;){
45-
if(!counterIndex.containsKey(diffCounter[i])){
46-
counterIndex.put(diffCounter[i], i-1);
44+
for (int i = 1, j = diffCounter.length - 1; i < j; ) {
45+
if (!counterIndex.containsKey(diffCounter[i])) {
46+
counterIndex.put(diffCounter[i], i - 1);
4747
i++;
48-
}else {
49-
return s.substring(i,j);
48+
} else {
49+
return s.substring(i, j);
5050
}
51-
if(!counterIndex.containsKey(diffCounter[j])){
52-
counterIndex.put(diffCounter[j], j-1);
51+
if (!counterIndex.containsKey(diffCounter[j])) {
52+
counterIndex.put(diffCounter[j], j - 1);
5353
j--;
54-
}else {
55-
return s.substring(i-1,j);
54+
} else {
55+
return s.substring(i - 1, j);
5656
}
5757
}
5858
return "";

0 commit comments

Comments
 (0)