An iterator is an object whose job is to move through a sequence and select each object in that sequence without the client programmer knowing or caring about the underlying structure of that sequence. In addition, an iterator is usually what’s called a lightweight object: one that’s cheap to create.

To design an iterator is not generating all the results once and retrieve it one by one. Instead we can put the elements
into a stack to generate one by one and return the value.

Get the next object in the sequence with next( ).

See if there are any more objects in the sequence with hasNext( ).

Remove the last element returned by the iterator with remove( ).An Iterator will also remove the last element produced by next( ), which means you must call next( ) before you call remove( ).

Stack方向

341. Flatten Nested List Iterator

Prepare the flatten integer during the hasNext( ). Next( ) 只用直接调用 when calling next it will return the next integer in the current nested list. we should not assume that hasnext is called before next( ).

Push the nestedInteger in reverse order to stack!

import java.util.Iterator;

public class NestedIterator implements Iterator<Integer> {
    public Stack<NestedInteger> stack;
    public NestedIterator(List<NestedInteger> nestedList) {
        // Initialize your data structure here.
        stack = new Stack<NestedInteger>();
        flatten(nestedList);
    }

    // @return {int} the next element in the iteration
    @Override
    public Integer next() {
        if(!hasNext())return null;
        return stack.pop().getInteger();
    }

    // @return {boolean} true if the iteration has more element or false
    @Override
    public boolean hasNext() {
        while(!stack.isEmpty() && !stack.peek().isInteger()){
            flatten(stack.pop().getList());
        }
        return !stack.isEmpty();
        // Write your code here

    }

    @Override
    public void remove() {
    }

    public void flatten(List<NestedInteger> list){
        for(int i = list.size() - 1;i >= 0;i--){
            stack.push(list.get(i));
        }
    }
}

251. Flatten 2D Vector

这种题怎么说有很多种实现方法两种Iterator维护 list的和list里面的可以把list里面的当作stack 在hasNext( ) 准备好list里面单个的

public class Vector2D implements Iterator<Integer> {
    private Iterator<List<Integer>> i;
    private Iterator<Integer> j;
    public Vector2D(List<List<Integer>> vec2d) {
        i = vec2d.iterator();
    }

    @Override
    public Integer next() {
        hasNext();
        return j.next();
    }

    @Override
    public boolean hasNext() {
       while((j == null || !j.hasNext()) && i.hasNext()){
            j = i.next().iterator();
       }
        return j != null && j.hasNext();
    }
}

173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Callingnext()will return the next smallest number in the BST.

Note:next()andhasNext()should run in average O(1) time and uses O(h) memory, wherehis the height of the tree.

本质上是In-Order Traversal left - root - right

顺着root的左子数依次保存左边的节点弹出的时候检查被弹出的节点是否有右边的子树如果有需要保存检查是否有next

如果有则先处理这个部分

public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<>();
    TreeNode next = null;
    void AddNodeToStack(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    } 

    // @param root: The root of binary tree.
    public BSTIterator(TreeNode root) {
        next = root;
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        if (next != null) {
            AddNodeToStack(next);
            next = null;
        }
        return !stack.isEmpty();
    }

    //@return: return next node
    public TreeNode next() {
        if (!hasNext()) {
            return null;
        }
        TreeNode cur = stack.pop();
        next = cur.right;
        return cur;
    }
}

Iterator