Skip to content

Commit 937861a

Browse files
add 230
1 parent c96e5d2 commit 937861a

File tree

3 files changed

+100
-0
lines changed

3 files changed

+100
-0
lines changed

README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -254,6 +254,7 @@ Your ideas/fixes/algorithms are more than welcome!
254254
|235|[Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/_235.java)| O(h)|O(1) | Easy| DFS
255255
|233|[Number of Digit One](https://leetcode.com/problems/number-of-digit-one/)|[Solution](../master/src/main/java/com/stevesun/solutions/NumberofDigitOne.java)| O(n)|O(1) | Hard| Math
256256
|232|[Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/)|[Solution](../master/src/main/java/com/stevesun/solutions/_232.java)| O(n)|O(n) | Medium| Stack, Design
257+
|230|[Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)|[Solution](../master/src/main/java/com/stevesun/solutions/_230.java)| O(n)|O(k) | Medium| Tree
257258
|229|[Majority Element II](https://leetcode.com/problems/majority-element-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/MajorityElementII.java)| O(n)|O(n) | Medium|
258259
|228|[Summary Ranges](https://leetcode.com/problems/summary-ranges/)|[Solution](../master/src/main/java/com/stevesun/solutions/SummaryRanges.java)| O(n)|O(1) | Medium| Array
259260
|226|[Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/InvertBinaryTree.java)| O(n)|O(h) | Easy| DFS, recursion
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.stevesun.solutions;
2+
3+
import com.stevesun.common.classes.TreeNode;
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
8+
/**
9+
* 230. Kth Smallest Element in a BST
10+
*
11+
* Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
12+
13+
Note:
14+
You may assume k is always valid, 1 ? k ? BST's total elements.
15+
16+
Follow up:
17+
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
18+
19+
*/
20+
public class _230 {
21+
22+
public static class MostNaiveWay {
23+
public int kthSmallest(TreeNode root, int k) {
24+
List<Integer> inorderList = new ArrayList<>();
25+
inorder(root, inorderList);
26+
return inorderList.get(k-1);
27+
}
28+
29+
private void inorder(TreeNode root, List<Integer> inorderList) {
30+
if (root == null) return;
31+
if (root.left != null) inorder(root.left, inorderList);
32+
inorderList.add(root.val);
33+
if (root.right != null) inorder(root.right, inorderList);
34+
return;
35+
}
36+
}
37+
38+
public static class BetterWay {
39+
int count = 0;
40+
int result = Integer.MIN_VALUE;
41+
public int kthSmallest(TreeNode root, int k) {
42+
inorder(root, k);
43+
return result;
44+
}
45+
46+
private void inorder(TreeNode root, int k) {
47+
if (root == null) return;
48+
inorder(root.left, k);
49+
count++;
50+
if (count == k) {
51+
result = root.val;
52+
return;
53+
}
54+
inorder(root.right, k);
55+
}
56+
}
57+
58+
}
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.common.classes.TreeNode;
4+
import com.stevesun.solutions._230;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertEquals;
9+
10+
/**
11+
* Created by stevesun on 5/19/17.
12+
*/
13+
public class _230Test {
14+
private static _230.MostNaiveWay naiveWay;
15+
private static _230.BetterWay betterWay;
16+
private static TreeNode root;
17+
private static int k;
18+
19+
@BeforeClass
20+
public static void setup(){
21+
naiveWay = new _230.MostNaiveWay();
22+
betterWay = new _230.BetterWay();
23+
}
24+
25+
@Test
26+
public void test1(){
27+
root = new TreeNode(1);
28+
k = 1;
29+
assertEquals(1, naiveWay.kthSmallest(root, k));
30+
assertEquals(1, betterWay.kthSmallest(root, k));
31+
}
32+
33+
@Test
34+
public void test2(){
35+
root = new TreeNode(2);
36+
root.left = new TreeNode(1);
37+
k = 1;
38+
assertEquals(1, naiveWay.kthSmallest(root, k));
39+
assertEquals(1, betterWay.kthSmallest(root, k));
40+
}
41+
}

0 commit comments

Comments
 (0)