Monday, June 27, 2016

[LeetCode] Flatten Nested List Iterator

Many questions looks pretty hard, and we came up lots of lines of code and tried to cover every corner cases. But in the end the perfect solution is always the simplest with least lines of code. The question is the example.

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?






No comments:

Post a Comment