341. Flatten Nested List Iterator

List里可以有int或者List，然后里面的List里面可以再有List.

用Stack来做比较直观

Iterator无非是next()或者hasNext()这2个方程

一开始我想的是hasNext()就简单的返还是不是空就行，主要的操作在next()里，结果发现无线循环。。好蠢

然后看网上答案改的在hasNext()里准备好，其实一开始的想法不一定错，二刷可以试试。

简单的说就是先都塞到STACK里面，如果Peek的元素是单一int就返还TRUE，然后next()会直接返还那个int。

如果不是单一int，是另一个List，那么把这个List给POP出来，再倒着塞回到stack。

再PEEK第一个，直到是单一INT。

当然，如果没元素了直接返还FALSE就行了，思路很清晰。。

    public Stack<NestedInteger> stack = new Stack<>();

    public NestedIterator(List<NestedInteger> nestedList) {

        for(int n = nestedList.size()-1; n >=0;n--)

        {

            stack.push(nestedList.get(n));

        }

    }

    @Override

    public Integer next()

    {

        if(hasNext()) return stack.pop().getInteger();

        else return null;

    }

    @Override

    public boolean hasNext() {

        while(!stack.isEmpty())

        {

            if(stack.peek().isInteger())

            {

                return true;

            }

            else

            {

                NestedInteger tempNested = stack.pop();

                for(int n = tempNested.getList().size()-1; n >= 0;n--)

                {

                    stack.push(tempNested.getList().get(n));

                }

            }

        }

        return false;

    }

感觉上不是特别难，但是牵扯到的别的概念太多了。

需要注意的是各种TYPE的DECLARE。

一开始挺接近的，使使劲说不定能做出来。

---

二刷没想到用STACK，用LIST楞做的。在constructor里直接遍历，Integer就加进去，Nested就展开。

有int加int，不是int展开继续加int。

最后就是一个list有所有int，然后就iterator.

public class NestedIterator implements Iterator<Integer> {

    List<Integer> list;

    public NestedIterator(List<NestedInteger> nestedList)

    {

        list = new ArrayList<Integer>();

        for(int i = 0; i < nestedList.size();i++)

        {

            if(nestedList.get(i).isInteger()) list.add(nestedList.get(i).getInteger());

            else

            {

                List<NestedInteger> tempList = new ArrayList<NestedInteger>(nestedList.get(i).getList());

                NestedIterator iter = new NestedIterator(tempList);

                while(iter.hasNext()) list.add(iter.next());

            }

        }

    }

    @Override

    public Integer next()

    {

        Integer res = new Integer(list.get(0));

        list.remove(0);

        return res;

    }

    @Override

    public boolean hasNext()

    {

        return list.size() != 0;

    }

}

一刷的做法是用stack，添加的时候不操作，遍历的时候进行判断和展开LIST的 操作。

二刷的做法是添加的时候都展了，遍历的时候不展了。 第一种时间上快一些。

---

---

三刷

这个题看起来挺难的，但是一刷二刷完全没有印象，回过头看了一下明白怎么回事了。

我一刷应该是看答案的做的，用的stack倒着加，每次POP出一个看是不是Integer，是的话返还，不是的话展开再加。比较直白的做法，需要消耗很大的空间，取决于Stack的大小，具体大小不好算，跟单一枝的宽度有关。

二刷更蠢= =直接完全展开，还不如一刷。。

三刷应该是很合理的，stack里存放的是Iterator,其实相当于保存了一个指针，我们通过pop来back track到当时的位置。。思想是DFS。

这个题更为关键的是应该抽象出树状图的概念，来做in Order。 i.isInteger()说明是一个leave，!i.isInteger()说明是新的subtree，此时要入栈记录位置，以便DFS的时候回到这里。

public class NestedIterator implements Iterator<Integer> {

    Stack<Iterator<NestedInteger>> stk;

    Iterator<NestedInteger> tempIter;

    Integer temp = null;

    public NestedIterator(List<NestedInteger> nestedList) {

        stk = new Stack<Iterator<NestedInteger>>();

        tempIter = nestedList.iterator();

        temp = findNextInt();

    }

    @Override

    public Integer next() {

        int res = temp;

        temp = findNextInt();

        return res;

    }

    public Integer findNextInt() {

        while (tempIter.hasNext() || !stk.isEmpty()) {

            if (tempIter.hasNext()) {

                NestedInteger i = tempIter.next();

                if (i.isInteger()) {

                    return i.getInteger();

                } else {

                    stk.push(tempIter);

                    tempIter = i.getList().iterator();

                }

            } else {

                tempIter = stk.pop();

            }

        }

        return null;

    }

    @Override

    public boolean hasNext() {

        return temp != null;

    }

}