(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);
      }
  }

댓글

이 블로그의 인기 게시물

(네트워크)폴링방식 vs 롱 폴링방식

(ElasticSearch) 결과에서 순서 정렬

(18장) WebSocekt과 STOMP를 사용하여 메시징하기