By Long Luo
This article is the solution 2 Approaches: DFS and Iteration(Using Stack) of Problem 341. Flatten Nested List Iterator.
Here are 2 approaches to solve this problem in Java, DFS and Iteration approach.
DFS
We can store all the integers in an array, just traversing the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| public class NestedIterator implements Iterator<Integer> { List<Integer> numList; int idx;
public NestedIterator(List<NestedInteger> nestedList) { numList = new ArrayList<>(); idx = 0; dfs(nestedList); }
private void dfs(List<NestedInteger> nestedList) { if (nestedList == null) { return; }
for (int i = idx; i < nestedList.size(); i++) { NestedInteger nested = nestedList.get(i); if (nested.isInteger()) { numList.add(nested.getInteger()); } else { dfs(nested.getList()); } } }
@Override public Integer next() { return numList.get(idx++); }
@Override public boolean hasNext() { if (idx < numList.size()) { return true; }
return false; } }
|
Analysis
Iteration (Using Stack)
We can use a Stack to maintain all nodes on the path from the root node to the current node.
The stack stores the iterators, which is a pointer to the element.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| public class NestedIterator implements Iterator<Integer> { Deque<Iterator<NestedInteger>> stk;
public NestedIterator(List<NestedInteger> nestedList) { stk = new ArrayDeque<>(); stk.push(nestedList.iterator()); }
@Override public Integer next() { return stk.peek().next().getInteger(); }
@Override public boolean hasNext() { while (!stk.isEmpty()) { Iterator<NestedInteger> iterator = stk.peek(); if (!iterator.hasNext()) { stk.pop(); continue; }
NestedInteger nested = iterator.next(); if (nested.isInteger()) { List<NestedInteger> list = new ArrayList<>(); list.add(nested); stk.push(list.iterator()); return true; }
stk.push(nested.getList().iterator()); }
return false; } }
|
Analysis
The Iteration approach is better.
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗