LeetCode341 Flatten Nested List Iterator（迭代器方式实践）
题目：
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list – whose elements may also be integers or other lists.
Example 1:
Given the list [[1,1],2,[1,1]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
分析：
先来看看leetcode给出的接口定义：
public class NestedIterator implements Iterator<Integer> {
public NestedIterator(List<NestedInteger> nestedList) {
}
@Override
public Integer next() {
}
@Override
public boolean hasNext() {
}
}// This is the interface that allows for creating nested lists.
// You should not implement it, or speculate about its implementation
public interface NestedInteger {
// @return true if this NestedInteger holds a single integer, rather than a
// nested list.
public boolean isInteger();
// @return the single integer that this NestedInteger holds, if it holds a
// single integer
// Return null if this NestedInteger holds a nested list
public Integer getInteger();
// @return the nested list that this NestedInteger holds, if it holds a
// nested list
// Return null if this NestedInteger holds a single integer
public List<NestedInteger> getList();
}综合题目和给出的接口定义，我们知道每一个NestedInteger实际上是一棵树，所有的Integer就是树的全部叶子节点，我们要遍历的nestedList其实就是NestedInteger组成的森林。对nestedList中树的遍历，我们从左向右遍历，对每一颗树，我们采用后根遍历，最后得出的结果就是题目要求的。我是根据这个思路来完成这道题的。
但是，遍历这些树可没有说起来那么简单。有两个难点，一，它不是一颗常规的树，比如我们熟悉的二叉树或DOM树；二，我们不仅仅是遍历完整棵树就了事，而是在遍历过程中，要中断，就像让你骑单车，但是每前进一米就必须停一秒一样，这导致我们不能用递归。对一个难点，还好应付，对象毕竟是一棵树，遍历它，思路清晰，不能用递归，就用迭代法吧。第二个难点，就有点难搞了，中断就意味着我们要记录中断时的状态，就像CPU中断一个线程时要保存它的状态一样，而且这里保存的是中断时状态的下一个状态，这样当返回时，就直接进入保存的状态就行了。我用两个栈加一个整数来记录一个状态，一个栈存储一个元素（Integer）的所有祖先节点（List），另一个栈和第一个栈对应，其中存储着另一个栈中对应元素在其父节点（List）中的索引位置，整数存储当前元素（Integer）在其父节点中（List）的索引位置。那么怎么寻找当前状态的下一个状态呢？先找当前元素的右兄弟节点，如果存在且该节点是Integer，它就是下一个元素，记录它的状态只需要将记录当前状态的整数加1即可，两个栈的值不变…另外的说起来就太抽象了，大家还是看代码吧。用一句话来总结这里遍历树的方法：类似用迭代的方法后跟遍历二叉树。
上一段说了一大堆，主要就是想说，直接遍历题目中给的集合，太不容易了。可是，当我们实现了题目要求的该集合的迭代器，再来遍历这个集合，就太太简单了。这就是迭代器的威力。关于迭代器，有个迭代器模式，这个模式的思想就是封装遍历一个集合的行为。本题是我见过的最能诠释迭代器模式思想的例子了，所以分享给大家。
下面是我对本题的解答：
public class NestedIterator implements Iterator<Integer> {
// 这其实是一个森林，森林里有nestedList.size()这么多棵树
private List<NestedInteger> nestedList;
// 从上到下的list，每个list的元素个数都大于0
LinkedList<List<NestedInteger>> ancestorsStack = new LinkedList<>();
// 与ancestorsStack对应，记录每个List<NestedInteger>在父list中的索引位置，
// 根list在父list中的位置设为-1
LinkedList<Integer> positionsStack = new LinkedList<Integer>();
// 下一个元素(Integer)在父list中的索引位置
private int integerIndex = 0;
public NestedIterator(List<NestedInteger> nestedList) {
this.nestedList = nestedList;
if (nestedList.size() == 0) {
return;
}
ancestorsStack.push(nestedList);
positionsStack.push(-1);
// 第一个被检查的元素
NestedInteger cursor = nestedList.get(0);
// 第一个被检查的元素在父list中的索引位置
int thisIndex = 0;
findNextElement(cursor, thisIndex);
}
@Override
public Integer next() {
Integer result = ancestorsStack.peek().get(integerIndex).getInteger();
if (integerIndex != ancestorsStack.peek().size() - 1
&& ancestorsStack.peek().get(integerIndex + 1).isInteger()) {
// 直接指向右边的Integer
integerIndex++;
return result;
}
int indexTemp = integerIndex;
// 往上
if (integerIndex == ancestorsStack.peek().size() - 1) {
// 寻找ancestorsStack中下一个元素的最近祖先
ancestorsStack.pop();
indexTemp = positionsStack.pop();
while (!ancestorsStack.isEmpty()) {
List<NestedInteger> temp = ancestorsStack.peek();
int size = temp.size();
if (indexTemp != size - 1) {
break;
} else {
ancestorsStack.pop();
indexTemp = positionsStack.pop();
}
}
}
// 这里隐含了integerIndex != ancestorsStack.peek().size() - 1
// && ！ancestorsStack.peek().get(integerIndex + 1).isInteger()的情况，因为
// 这种情况下，ancestorsStack、positionsStack、start和indexTemp已经处于我们希望的
// 状态
if (ancestorsStack.isEmpty()) {
return result;
}
// 以ancestorsStack.peek().get(indexTemp + 1)作为起点寻找第一个Integer
NestedInteger start = ancestorsStack.peek().get(indexTemp + 1);
int thisIndex = indexTemp + 1;
findNextElement(start, thisIndex);
return result;
}
/**
* 以ancestorsStack、positions、start和startIndex共同定位的元素为起点，搜索下一个Integer
* @param cursor 第一个被检查的元素
* @param thisIndex 第一个被检查的元素在父list中的索引位置
*/
private void findNextElement(NestedInteger start, int startIndex) {
NestedInteger cursor = start;
int thisIndex = startIndex;
boolean findNext = false;
while (!findNext) {
if (cursor.isInteger()) {
integerIndex = thisIndex;
findNext = true;
} else {
if (cursor.getList().size() != 0) {
// 往下走
ancestorsStack.push(cursor.getList());
positionsStack.push(thisIndex);
thisIndex = 0;
cursor = cursor.getList().get(thisIndex);
} else {
if (thisIndex < ancestorsStack.peek().size() - 1) {
// 往右走
thisIndex++;
cursor = ancestorsStack.peek().get(thisIndex);
} else {
// 往上走
ancestorsStack.pop();
thisIndex = positionsStack.pop();
while (!ancestorsStack.isEmpty()) {
List<NestedInteger> temp = ancestorsStack.peek();
int size = temp.size();
if (thisIndex != size - 1) {
thisIndex++;
cursor = ancestorsStack.peek().get(thisIndex);
break;
} else {
ancestorsStack.pop();
thisIndex = positionsStack.pop();
}
}
if (ancestorsStack.isEmpty()) {
break;
}
}
}
}
}
}
@Override
public boolean hasNext() {
return !ancestorsStack.isEmpty();
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
}本文提供了解该题最直观的方法，但不是最优的，大家可以在此基础上任意优化。