Java concise solution.


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

  • 0

    Does your next() run in average O(1) time?


  • 0
    S

    This ran in 5 ms.... not too terrible... I like the concise solution above as well where the complete inorder doesn't happen on construction...

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
        public class BSTIterator {
            
            Iterator<Integer> iterator;
        
            public BSTIterator(TreeNode root) 
            {
                List<Integer> inorder = new ArrayList<>();
                inOrder(root, inorder);
                iterator = inorder.iterator();
            }
            
            private void inOrder(TreeNode node, List<Integer> inOrder)
            {
                if(node != null)
                {
                    inOrder(node.left, inOrder);
                    inOrder.add(node.val);
                    inOrder(node.right, inOrder);
                }
            }
            
        
            /** @return whether we have a next smallest number */
            public boolean hasNext() {
                return iterator.hasNext();
            }
        
            /** @return the next smallest number */
            public int next() {
                return iterator.next();
            }
        }
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = new BSTIterator(root);
     * while (i.hasNext()) v[f()] = i.next();
     */
    

  • 0
    S

    The code above has a space complexity of O(number of nodes) and the question demands O(height of tree at most) also the recursion in the iterator constructor again uses more memory. At times it does not matter if it takes more running time as long as the requirement is full filled. The original code above is efficient and concise.


Log in to reply
 

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