(Alogrithm) Binary Search Tree Iterable
with Binary Search Tree, To require O(1) average Time(amortized analysis)
and O(h) space.
O(h) 공간을 만족하기 위해서, 루트 노드의 왼쪽값만 저장한다.
그 후 next()값을 호출시, 방금 출력된 값보다 큰 root.right를 삽입하여
O(h) 공간을 만족시킨다.
Stack<TreeNode> treeList;
public BinarySearchIterable(TreeNode root) {
while(root != null) {
treeList.push(root);
root = root.left;
}
}
public boolean hasNext() {
if(treeList.isEmpty())
return false;
return true;
}
public int next() {
if(hasNext()) {
TreeNode n = treeList.pop();
int value = n.value;
treeList.push(n.right);
}
}
and O(h) space.
O(h) 공간을 만족하기 위해서, 루트 노드의 왼쪽값만 저장한다.
그 후 next()값을 호출시, 방금 출력된 값보다 큰 root.right를 삽입하여
O(h) 공간을 만족시킨다.
Stack<TreeNode> treeList;
public BinarySearchIterable(TreeNode root) {
while(root != null) {
treeList.push(root);
root = root.left;
}
}
public boolean hasNext() {
if(treeList.isEmpty())
return false;
return true;
}
public int next() {
if(hasNext()) {
TreeNode n = treeList.pop();
int value = n.value;
treeList.push(n.right);
}
}
댓글
댓글 쓰기