[leetcode] Binary Search Tree Iterator

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

public class BSTIterator { Stack<TreeNode> stack = new Stack<TreeNode>(); public BSTIterator(TreeNode root) { while (root != null){ stack.push(root); root = root.left; } } /** @return whether we have a next smallest number */ public boolean hasNext() { return !stack.isEmpty(); } /** @return the next smallest number */ public int next() { TreeNode next = stack.pop(); TreeNode node = next.right; while (node != null){ stack.push(node); node = node.left; } return next.val; } }