Really clean Java solution with one Stack


  • 1
    Z

    The general idea is simple:

    1. When initialize the iterator, we push all the nodes along the left most path into the stack.
    2. During the iteration, whenever a node gets popped out, push it's right node (if not null) and it's left child node into the stack (similar as step 1).
    3. When there's no more nodes in stack then the iteration is over.
    public class BSTIterator {
        
        Stack<TreeNode> stack;
    
        public BSTIterator(TreeNode root) {
            stack = new Stack<>();
            pushTillLeftMost(root);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            TreeNode node = stack.pop();
            pushTillLeftMost(node.right);
            return node.val;
        }
        
        public void pushTillLeftMost(TreeNode node) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.