-
Notifications
You must be signed in to change notification settings - Fork 1
/
FlattenNestedListIterator.java
59 lines (49 loc) · 1.49 KB
/
FlattenNestedListIterator.java
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* 341. Flatten Nested List Iterator
* DFS
* @author LBW
*/
public class FlattenNestedListIterator implements Iterator<Integer>{
private List<Integer> values = new ArrayList<>();
private Iterator<Integer> it;
public FlattenNestedListIterator(List<NestedInteger> nestedList) {
traverse(nestedList);
it = values.iterator();
}
@Override
public Integer next() {
return it.next();
}
@Override
public boolean hasNext() {
return it.hasNext();
}
private void traverse(List<NestedInteger> nestedList) {
for (NestedInteger ni: nestedList) {
dfs(ni);
}
}
private void dfs(NestedInteger ni) {
if (ni.isInteger()) {
values.add(ni.getInteger());
}
else {
for (NestedInteger nni: ni.getList()) {
dfs(nni);
}
}
}
}
interface NestedInteger {
// @return true if this NestedInteger holds a single integer, rather than a nested list.
public boolean isInteger();
// @return the single integer that this NestedInteger holds, if it holds a single integer
// Return null if this NestedInteger holds a nested list
public Integer getInteger();
// @return the nested list that this NestedInteger holds, if it holds a nested list
// Return null if this NestedInteger holds a single integer
public List<NestedInteger> getList();
}