Beats 88.80% java based solution using a queue


  • 0

    So, it turns out that if you're willing to violate the requirement then you could get some performance improvement. The following solution simply front-loads the heavy-lifting in the constructor where stores an in-order sequence of the tree in a queue. This is desirable if the number of times next() or hasNext() will be invoked by some factor of N. However, if not, then this is doing unnecessary work and won't earn you any points. Regardless, below is the implementation:

    Queue<TreeNode> q = new LinkedList<TreeNode>();
    
    public BSTIterator(TreeNode root) {
        populateQueue(root, q);
    }
    
    private void populateQueue(TreeNode root, Queue<TreeNode> q) {
        if (root == null) return;
        populateQueue(root.left, q);
        q.add(root);
        populateQueue(root.right, q);
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !q.isEmpty();
    }
    
    /** @return the next smallest number */
    public int next() {
        return q.poll().val;
    }
    

    Note: The OJ is very finicky. You may have made a couple of observations after reading the above code:

    • Why have a queue of type TreeNode; just store the integers instead?
    • Why pass the queue around as an argument in the method when it's an instance variable anyway?

    Turns out that when I change things up to a more "natural" implementation for this requirement-perversion, I score 45%! I'm not entirely sure why this happens, but it's been reproducible over the last 30mins. Anyway, thought i'd share; who knows, this may be some silly hack that could help others score higher in other questions lol.


  • 0
    K

    this is the most basic solution.
    And I tested your code.
    it shows the performance is beaten by(rather than beats) 88.80% solutions....


Log in to reply
 

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