This is the link to the problem: 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]
.The solution is pretty straightforward, if we treat the nested list to a tree, with nested list as children nodes, its parent is the list encloses it. Then we can use pre-order traversal of the tree to find the all of the integers and print them out. But to implement the iterator, we also need a stack to keep track the parent list when we travel the children lists underneath it. Remember the solution of pre-order traversal of binary search using stack?