You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.
Implement the NestedIterator class:
NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
int next() Returns the next integer in the nested list.
boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.
Your code will be tested with the following pseudocode:
initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res
If res matches the expected flattened list, then your code will be judged as correct.
Example 1:
Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
Constraints:
1 <= nestedList.length <= 500
The values of the integers in the nested list is in the range [-106, 106].
public class NestedInteger {
// 如果其中存的是一个整数，则返回 true，否则返回 false
public boolean isInteger();
// 如果其中存的是一个整数，则返回这个整数，否则返回 null
public Integer getInteger();
// 如果其中存的是一个列表，则返回这个列表，否则返回 null
public List<NestedInteger> getList();
}
public class NestedIterator implements Iterator<Integer> {
// 构造器输入一个 NestedInteger 列表
public NestedIterator(List<NestedInteger> nestedList) {}
// 返回下一个整数
public Integer next() {}
// 是否还有下一个整数？
public boolean hasNext() {}
}
NestedIterator i = new NestedIterator(nestedList);
while (i.hasNext())
print(i.next());
You should not implement it, or speculate about its implementation.
public class NestedInteger {
private Integer val;
private List<NestedInteger> list;
public NestedInteger(Integer val) {
this.val = val;
this.list = null;
}
public NestedInteger(List<NestedInteger> list) {
this.list = list;
this.val = null;
}
// 如果其中存的是一个整数，则返回 true，否则返回 false
public boolean isInteger() {
return val != null;
}
// 如果其中存的是一个整数，则返回这个整数，否则返回 null
public Integer getInteger() {
return this.val;
}
// 如果其中存的是一个列表，则返回这个列表，否则返回 null
public List<NestedInteger> getList() {
return this.list;
}
}
class NestedInteger { Integer val; List<NestedInteger> list;}/* 基本的 N 叉树节点 */class TreeNode { int val; TreeNode[] children;}
class NestedInteger {
Integer val;
List<NestedInteger> list;
}
/* 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}
class NestedIterator implements Iterator<Integer> {
private Iterator<Integer> it;
public NestedIterator(List<NestedInteger> nestedList) {
// 存放将 nestedList 打平的结果
List<Integer> result = new LinkedList<>();
for (NestedInteger node : nestedList) {
// 以每个节点为根遍历
traverse(node, result);
}
// 得到 result 列表的迭代器
this.it = result.iterator();
}
public Integer next() {
return it.next();
}
public boolean hasNext() {
return it.hasNext();
}
// 遍历以 root 为根的多叉树，将叶子节点的值加入 result 列表
private void traverse(NestedInteger root, List<Integer> result) {
if (root.isInteger()) {
// 到达叶子节点
result.add(root.getInteger());
return;
}
// 遍历框架
for (NestedInteger child : root.getList()) {
traverse(child, result);
}
}
}
public class NestedIterator implements Iterator<Integer> {
private LinkedList<NestedInteger> list;
public NestedIterator(List<NestedInteger> nestedList) {
// 不直接用 nestedList 的引用，是因为不能确定它的底层实现
// 必须保证是 LinkedList，否则下面的 addFirst 会很低效
list = new LinkedList<>(nestedList);
}
public Integer next() {
// hasNext 方法保证了第一个元素一定是整数类型
return list.remove(0).getInteger();
}
public boolean hasNext() {
// 循环拆分列表元素，直到列表第一个元素是整数类型
while (!list.isEmpty() && !list.get(0).isInteger()) {
// 当列表开头第一个元素是列表类型时，进入循环
List<NestedInteger> first = list.remove(0).getList();
// 将第一个列表打平并按顺序添加到开头
for (int i = first.size() - 1; i >= 0; i--) {
list.addFirst(first.get(i));
}
}
return !list.isEmpty();
}
}