my java solution using PriorityQueue


  • 1
    Y
    public class BSTIterator {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        public BSTIterator(TreeNode root) {
            helper(root);
        }
        
        public void helper(TreeNode root) {
            if(root == null) return;
            helper(root.left);
            heap.add(root.val);
            helper(root.right);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return heap.size() != 0;
        }
    
        /** @return the next smallest number */
        public int next() {
            return heap.poll();
        }
    }
    

    Both my function calls cost O(1) time and space, because I used extra O(n) time/space to construct the heap.


  • 0
    H

    The most excellent and greatest coder I have ever seen all over the world!


Log in to reply
 

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