Description:
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:
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].
Link:
https://leetcode.com/problems/flatten-nested-list-iterator/description/
解题方法：
NestedIterator：
将vector里面的NestedInteger反过来亚入栈。
hasNext：
如果栈顶的NestedInteger是一个单独的数则返回true，否则从栈顶的这个List取出其中的NestedInteger，再反过来压栈，直到栈顶的元素是单独的数。
next：
从栈顶取出数即可。
Time Complexity：
NestedIterator：O(N)
next：O(1)
完整代码：
class NestedIterator
{
private:
stack<NestedInteger> container;
public:
NestedIterator(vector<NestedInteger> &nestedList)
{
for(int i = nestedList.size() - 1; i >= 0; i--)
{
container.push(nestedList[i]);
}
}
int next()
{
int result = container.top().getInteger();
container.pop();
return result;
}
bool hasNext()
{
while(!container.empty())
{
NestedInteger curr = container.top();
if(curr.isInteger())
return true;
container.pop();
vector<NestedInteger> & currList = curr.getList();
for(int i = currList.size() - 1; i >= 0; i--)
{
container.push(currList[i]);
}
}
return false;
}
};
