Iterator 类

Zigzag Iterator

所谓的 Zigzag 其实等价于 circular ~ 实现 circular 的常见办法有两个：

• 建 array / arraylist，靠取 mod 的 index trick;

• 直接用内置的 deque 库，每次头尾操作就可以

public class ZigzagIterator {
    Deque<Iterator<Integer>> deque;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        deque = new LinkedList<Iterator<Integer>>();
        if(v1.size() != 0) deque.offerFirst(v1.iterator());
        if(v2.size() != 0) deque.offerFirst(v2.iterator());
    }

    public int next() {
        Iterator<Integer> iter = deque.pollLast();
        int num = iter.next();
        if(iter.hasNext()) deque.offerFirst(iter);
        return num;
    }

    public boolean hasNext() {
        return (deque.size() != 0);
    }
}

Peeking Iterator

由于先做了 Flatten Nested List Iterator 的 peeking iterator 实现，做这题简直毫无压力。。。

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {

    Integer peek;
    Iterator<Integer> cur;

    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        cur = iterator;
        peek = internalNext();
    }

    private Integer internalNext(){
        if(cur.hasNext()){
            return cur.next();
        } else {
            return null;
        }
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return peek;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer tmp = peek;
        peek = internalNext();
        return tmp;
    }

    @Override
    public boolean hasNext() {
        return (peek != null);
    }
}

Flatten 2D Vector

依然是没啥难度。。迭代器好简单。。

public class Vector2D implements Iterator<Integer> {
    Iterator<List<Integer>> listIter;
    Iterator<Integer> cur;
    Integer peek;

    public Vector2D(List<List<Integer>> vec2d) {
        listIter = vec2d.iterator();
        peek = internalNext();
    }

    private Integer internalNext(){
        if(cur != null && cur.hasNext()){
            return cur.next();
        } else if(listIter.hasNext()){
            cur = listIter.next().iterator();
            return internalNext();
        } else {
            return null;
        }
    }

    @Override
    public Integer next() {
        Integer tmp = peek;
        peek = internalNext();
        return tmp;
    }

    @Override
    public boolean hasNext() {
        return (peek != null);
    }
}

Flatten Nested List Iterator

之前准备 LinkedIn 的时候做过，拿来重用下。

首先我不太认同 LC 的 test case 里没有重复的 hasNext() 调用的情况。。把执行逻辑全堆到 hasNext() 里是有问题的。

关键在于 internalNext() 的实现，还有巧妙递归调用自己减少代码量的实现方式。

• 如果 cur Iterator 还有货，就遍历；

• 遍历出来的是 Integer，就可以直接设 instance variable 了；

• 遍历出来的是 List，说明下面还有子树，先把当前的存 Stack 上，cur 指到下面，再调用自己一次；

• cur 没货了，从 stack 里取一个，接着搞；

• stack 也没货了，就只能返回 null 了 ...

public class NestedIterator implements Iterator<Integer> {

    private Integer peek;
    private Stack<Iterator<NestedInteger>> stack;
    private Iterator<NestedInteger> curIter;

    public NestedIterator(List<NestedInteger> nestedList) {
        curIter = nestedList.iterator();
        stack = new Stack<>();
        peek = internalNext();
    }

    private Integer internalNext(){
        if(curIter.hasNext()){
            NestedInteger node = curIter.next();
            if(node.isInteger()){
                return node.getInteger();
            } else {
                stack.push(curIter);
                curIter = node.getList().iterator();

                return internalNext();
            }
        } else if(!stack.isEmpty()){
            curIter = stack.pop();

            return internalNext();
        } else {
            return null;
        }
    }

    @Override
    public Integer next() {
        Integer rst = peek;
        peek = internalNext();
        return rst;
    }

    @Override
    public boolean hasNext() {
        return (peek != null);
    }
}

Binary Search Tree Iterator

顺着这个思路设计的话，BST iterator 也可以做。不过因为 TreeNode 不自带 iterator，往右子树跳的那一下，得自己手动写。

public class BSTIterator {

    Stack<TreeNode> stack;
    TreeNode cur;
    TreeNode peek;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        cur = root;
        peek = internalNext();
    }

    private TreeNode internalNext(){
        if(cur != null){
            if(cur.left != null){
                stack.push(cur);
                cur = cur.left;
                return internalNext();
            } else {
                TreeNode tmp = cur;
                cur = cur.right;
                return tmp;
            }
        } else if (!stack.isEmpty()){
            TreeNode tmp = stack.pop();
            cur = tmp.right;
            return tmp;
        } else {
            return null;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return (peek != null);
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = peek;
        peek = internalNext();
        return node.val;
    }
}

这题的另一种画风比较常规的写法就是 in-order traversal ~

public class BSTIterator {
    Stack<TreeNode> stack;
    TreeNode cur;
    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode>();
        cur = root;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return (!stack.isEmpty() || cur != null);
    }

    /** @return the next smallest number */
    public int next() {
        while(cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode node = stack.pop();
        cur = node.right;
        return node.val;
    }
}

(FB) Binary Tree Post-order iterator

据群内小伙伴表示是 FB 高频提题，自己就写 test case 试试看。

其实这题就是考你到底会不会写只依靠 stack + cur + prev 指针的迭代写法，如果会了，这题就做出来了。

import java.util.*;

public class Main {
    private static class TreeNode {
        int val;
        TreeNode left, right;
        public TreeNode(int val){
            this.val = val;
        }
    }

    private static class PostOrderIterator implements Iterator<TreeNode>{
        Stack<TreeNode> stack;
        TreeNode cur;
        TreeNode prev;
        public PostOrderIterator(TreeNode root){
            stack = new Stack<>();
            cur = root;
            prev = null;
            if(cur != null) stack.push(cur);
        }
        public boolean hasNext(){
            return (!stack.isEmpty());
        }
        public TreeNode next(){
            TreeNode rst = null;

            while(!stack.isEmpty()){
                cur = stack.peek();
                if(prev == null || prev.left == cur || prev.right == cur){
                    if(cur.left != null){
                        stack.push(cur.left);
                    } else if(cur.right != null){
                        stack.push(cur.right);
                    }
                } else if(cur.left == prev){
                    if(cur.right != null) stack.push(cur.right);
                } else {
                    rst = cur;
                    stack.pop();
                }
                prev = cur;
                if(rst != null) break;
            }

            return rst;
        }
    }

    public static void main(String[] args){
        /*
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        node7.left = node3;
        node7.right = node6;
        node3.left = node1;
        node3.right = node2;
        node6.left = node5;
        node5.right = node4;
        */

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);

        node10.left = node5;
        node10.right = node9;
        node5.left = node2;
        node5.right = node4;
        node2.left = node1;
        node4.left = node3;
        node9.left = node6;
        node9.right = node8;
        node8.left = node7;

        PostOrderIterator iter = new PostOrderIterator(node10);

        while(iter.hasNext()){
            System.out.println(iter.next().val);
        }

    }
}