-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_230.java
More file actions
39 lines (31 loc) · 908 Bytes
/
Copy pathP_230.java
File metadata and controls
39 lines (31 loc) · 908 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package leetcode.medium;
import java.util.ArrayDeque;
import java.util.Deque;
import utils.DataStructures.TreeNode;
public class P_230 {
static class BSTIterator {
Deque<TreeNode> stack;
BSTIterator(TreeNode root) {
stack = new ArrayDeque<>();
traverseLeft(root);
}
int next() {
final TreeNode treeNode = stack.removeFirst();
traverseLeft(treeNode.right);
return treeNode.val;
}
void traverseLeft(TreeNode curr) {
while (curr != null) {
stack.addFirst(curr);
curr = curr.left;
}
}
}
public int kthSmallest(TreeNode root, int k) {
final BSTIterator bstIterator = new BSTIterator(root);
for (int i = 1; i < k; i++) {
bstIterator.next();
}
return bstIterator.next();
}
}