Iterator 类
所谓的 Zigzag 其实等价于 circular ~ 实现 circular 的常见办法有两个：
建 array / arraylist，靠取 mod 的 index trick;
直接用内置的 deque 库，每次头尾操作就可以
public class ZigzagIterator {
Deque<Iterator<Integer>> deque;
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
deque = new LinkedList<Iterator<Integer>>();
if(v1.size() != 0) deque.offerFirst(v1.iterator());
if(v2.size() != 0) deque.offerFirst(v2.iterator());
}
public int next() {
Iterator<Integer> iter = deque.pollLast();
int num = iter.next();
if(iter.hasNext()) deque.offerFirst(iter);
return num;
}
public boolean hasNext() {
return (deque.size() != 0);
}
}由于先做了 Flatten Nested List Iterator 的 peeking iterator 实现，做这题简直毫无压力。。。
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
Integer peek;
Iterator<Integer> cur;
public PeekingIterator(Iterator<Integer> iterator) {
// initialize any member here.
cur = iterator;
peek = internalNext();
}
private Integer internalNext(){
if(cur.hasNext()){
return cur.next();
} else {
return null;
}
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
return peek;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
Integer tmp = peek;
peek = internalNext();
return tmp;
}
@Override
public boolean hasNext() {
return (peek != null);
}
}依然是没啥难度。。迭代器好简单。。
public class Vector2D implements Iterator<Integer> {
Iterator<List<Integer>> listIter;
Iterator<Integer> cur;
Integer peek;
public Vector2D(List<List<Integer>> vec2d) {
listIter = vec2d.iterator();
peek = internalNext();
}
private Integer internalNext(){
if(cur != null && cur.hasNext()){
return cur.next();
} else if(listIter.hasNext()){
cur = listIter.next().iterator();
return internalNext();
} else {
return null;
}
}
@Override
public Integer next() {
Integer tmp = peek;
peek = internalNext();
return tmp;
}
@Override
public boolean hasNext() {
return (peek != null);
}
}之前准备 LinkedIn 的时候做过，拿来重用下。
首先我不太认同 LC 的 test case 里没有重复的 hasNext() 调用的情况。。把执行逻辑全堆到 hasNext() 里是有问题的。
关键在于 internalNext() 的实现，还有巧妙递归调用自己减少代码量的实现方式。
如果 cur Iterator 还有货，就遍历；
遍历出来的是 Integer，就可以直接设 instance variable 了；
遍历出来的是 List，说明下面还有子树，先把当前的存 Stack 上，cur 指到下面，再调用自己一次；
cur 没货了，从 stack 里取一个，接着搞；
stack 也没货了，就只能返回 null 了 ...
public class NestedIterator implements Iterator<Integer> {
private Integer peek;
private Stack<Iterator<NestedInteger>> stack;
private Iterator<NestedInteger> curIter;
public NestedIterator(List<NestedInteger> nestedList) {
curIter = nestedList.iterator();
stack = new Stack<>();
peek = internalNext();
}
private Integer internalNext(){
if(curIter.hasNext()){
NestedInteger node = curIter.next();
if(node.isInteger()){
return node.getInteger();
} else {
stack.push(curIter);
curIter = node.getList().iterator();
return internalNext();
}
} else if(!stack.isEmpty()){
curIter = stack.pop();
return internalNext();
} else {
return null;
}
}
@Override
public Integer next() {
Integer rst = peek;
peek = internalNext();
return rst;
}
@Override
public boolean hasNext() {
return (peek != null);
}
}顺着这个思路设计的话，BST iterator 也可以做。不过因为 TreeNode 不自带 iterator，往右子树跳的那一下，得自己手动写。
public class BSTIterator {
Stack<TreeNode> stack;
TreeNode cur;
TreeNode peek;
public BSTIterator(TreeNode root) {
stack = new Stack<>();
cur = root;
peek = internalNext();
}
private TreeNode internalNext(){
if(cur != null){
if(cur.left != null){
stack.push(cur);
cur = cur.left;
return internalNext();
} else {
TreeNode tmp = cur;
cur = cur.right;
return tmp;
}
} else if (!stack.isEmpty()){
TreeNode tmp = stack.pop();
cur = tmp.right;
return tmp;
} else {
return null;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return (peek != null);
}
/** @return the next smallest number */
public int next() {
TreeNode node = peek;
peek = internalNext();
return node.val;
}
}这题的另一种画风比较常规的写法就是 in-order traversal ~
public class BSTIterator {
Stack<TreeNode> stack;
TreeNode cur;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
cur = root;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return (!stack.isEmpty() || cur != null);
}
/** @return the next smallest number */
public int next() {
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
cur = node.right;
return node.val;
}
}(FB) Binary Tree Post-order iterator
据群内小伙伴表示是 FB 高频提题，自己就写 test case 试试看。
其实这题就是考你到底会不会写只依靠 stack + cur + prev 指针的迭代写法，如果会了，这题就做出来了。
import java.util.*;
public class Main {
private static class TreeNode {
int val;
TreeNode left, right;
public TreeNode(int val){
this.val = val;
}
}
private static class PostOrderIterator implements Iterator<TreeNode>{
Stack<TreeNode> stack;
TreeNode cur;
TreeNode prev;
public PostOrderIterator(TreeNode root){
stack = new Stack<>();
cur = root;
prev = null;
if(cur != null) stack.push(cur);
}
public boolean hasNext(){
return (!stack.isEmpty());
}
public TreeNode next(){
TreeNode rst = null;
while(!stack.isEmpty()){
cur = stack.peek();
if(prev == null || prev.left == cur || prev.right == cur){
if(cur.left != null){
stack.push(cur.left);
} else if(cur.right != null){
stack.push(cur.right);
}
} else if(cur.left == prev){
if(cur.right != null) stack.push(cur.right);
} else {
rst = cur;
stack.pop();
}
prev = cur;
if(rst != null) break;
}
return rst;
}
}
public static void main(String[] args){
/*
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
node7.left = node3;
node7.right = node6;
node3.left = node1;
node3.right = node2;
node6.left = node5;
node5.right = node4;
*/
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node10 = new TreeNode(10);
node10.left = node5;
node10.right = node9;
node5.left = node2;
node5.right = node4;
node2.left = node1;
node4.left = node3;
node9.left = node6;
node9.right = node8;
node8.left = node7;
PostOrderIterator iter = new PostOrderIterator(node10);
while(iter.hasNext()){
System.out.println(iter.next().val);
}
}
}Last updated