Lexi's Leetcode solutions

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)
        stack.push(root);
    }
    @Override
    public TreeNode next() {
      if (hasNext()) {
        TreeNode pop = stack.pop();
        if (pop.right != null)
          stack.push(pop.right);
        if (pop.left != null) 
          stack.push(pop.left);
        return pop;
      } else {
        throw new NoSuchElementException(); 
      }
    }
    @Override
    public boolean hasNext() {
      return !stack.isEmpty();
    }
  }
  @Override
  public Iterator<TreeNode> iterator() {
    return new TreeIterator(this.root);
  }
}