空间复杂度：O(n)
package com.chen.li.JDK_RBT.bstIterator;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
class BSTIterator {
private List<TreeNode> list = new ArrayList<TreeNode>();
private Iterator<TreeNode> it;
public BSTIterator(TreeNode root) {
if(root != null)
initList(root);
it = list.iterator();
}
private void initList(TreeNode node) {
if(node == null)
return;
if(node.left != null) {
initList(node.left);
}
list.add(node);
if(node.right != null) {
initList(node.right);
}
}
/** @return the next smallest number */
public int next() {
return it.next().val;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return it.hasNext();
}
}
空间复杂度 O( log(n) )
package com.chen.li.JDK_RBT.bstIterator;
import java.util.Stack;
public class BSTIterator2 {
Stack<TreeNode> stack = new Stack<>();
public BSTIterator2(TreeNode root) {
stackLeftNodes(root);
}
private void stackLeftNodes(TreeNode node) {
while(node != null) {
stack.push(node);
node = node.left;
}
}
/** @return the next smallest number */
public int next() {
TreeNode node = stack.pop();
stackLeftNodes(node.right);
return node.val;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
}
