Simple and Fast Java solution


  • 0
    B
    public class BSTIterator {
    
    private TreeNode helper;
    private Deque<TreeNode> stack;
    
    public BSTIterator(TreeNode root) {
        helper = root;
        stack = new LinkedList<TreeNode>();
        while(helper != null && helper.left != null) {
            stack.addFirst(helper);
            helper = helper.left;
        }
        // after initialized helper and stack, helper == null or helper == smallest node in BST
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return (helper == null && stack.isEmpty())? false: true;
    }
    
    /** @return the next smallest number */
    public int next() {
        // the average time complexity is O(1)
        while(helper != null && helper.left != null) {
            stack.addFirst(helper);
            helper = helper.left;
        }
        TreeNode cur = null;
        if(helper == null) {
            cur = stack.pollFirst();
        } else {
            cur = helper;
        }
        helper = cur.right;
        return cur.val;
    
    }
    

    }


Log in to reply
 

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