[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?

	public class NestedIterator implements Iterator<Integer> {
	//pointer the curr list we are examing
	List<NestedInteger> curr;
	//the index of the item in the list
	int pos;
	//all of the parent lists
	Stack<List<NestedInteger>> stack;
	//and the corresponding position in the parent lists before we go down to the childrent list
	Stack<Integer> posStack;
	public NestedIterator(List<NestedInteger> nestedList) {
	this.curr = nestedList;
	this.pos = 0;
	this.stack = new Stack<>();
	this.posStack = new Stack<>();
	}
	@Override
	public Integer next() {
	Integer result = null;
	result = curr.get(this.pos).getInteger();
	pos++;
	return result;
	}
	@Override
	public boolean hasNext() {
	//when the input is empty OR when we finish everything
	if(this.pos >= curr.size() && this.stack.isEmpty()){
	return false;
	}
	while(this.pos<curr.size() || !this.stack.isEmpty()){
	if(this.pos<curr.size()){
	if(this.curr.get(this.pos).isInteger())
	return true;
	else{
	if(curr.get(this.pos).getList().size()>0){
	//save parent and current postion in parent list
	this.stack.push(this.curr);
	this.posStack.push(this.pos);
	//then go down to the children level
	this.curr = curr.get(this.pos).getList();
	this.pos = 0;
	}else{
	this.pos++ ;
	}
	}
	}else{
	this.curr = this.stack.pop();
	this.pos = this.posStack.pop() + 1;
	}
	}
	return false;
	}
	}

view raw FlattenNestedListIterator hosted with ❤ by GitHub