Lexi's Leetcode solutions

Archive for August 22nd, 2013

Iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container’s elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled. It provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

这个模式可以保证不同的容器统一用一个interface来traverse,比如正常用for的话,array的traverse要用arr[i],arrayList的要用get(i),map更是得map.entrySet.get..,各种syntax不同,所以即使对每个element干的事儿一样,traverse也要写三遍,太麻烦了。如果用iterator,所有traverse统一用next()就行了。具体iterator是怎么next()的,自己再在容器里面写(大不了就三个容器都implement MyContainer,全写一遍next()函数对于该容器是怎么取下一个的。反正一劳永逸,next()一旦定义了,以后任何client都可以随便用)。其实对于ArrayList, Map之类这么长用的,java已经都给写好了iterator (e.g. List list = new List(); Iterator it = list.iterator();)。下面是例子:

  1. Container要implement Iterable<Type>
  2. Container里面写个implement Iterator<Type> 的iterator inner class
  3. Container里要有个iterator() method用来生成一个iterator
  4. Inner iterator class里面implement next(), hasNext()两个method.
public class TreeInPreOrderIterable implements Iterable<TreeNode> {
  private TreeNode root;
  private class TreeIterator implements Iterator<TreeNode> {
    Stack<TreeNode> stack;
    private TreeIterator(TreeNode root) {
      stack = new Stack<TreeNode>();
      if (root != null)
    public TreeNode next() {
      if (hasNext()) {
        TreeNode pop = stack.pop();
        if (pop.right != null)
        if (pop.left != null) 
        return pop;
      } else {
        throw new NoSuchElementException(); 
    public boolean hasNext() {
      return !stack.isEmpty();
  public Iterator<TreeNode> iterator() {
    return new TreeIterator(this.root);