Java O(1) next() and O(1) hasNext() solution


  • 0
    P
    public class BSTIterator {
    
        TreeNode root;
        List<TreeNode> list = new ArrayList<>();
        int current = 0;
        
        public BSTIterator(TreeNode root) {
            this.root = root;
            inOrder(root);
        }
        
        public void inOrder(TreeNode root){
            if(root == null){
                return;
            }
            inOrder(root.left);
            list.add(root);
            inOrder(root.right);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            if(current < list.size() && list.get(current) != null){
                return true;
            }
            return false;
        }
    
        /** @return the next smallest number */
        public int next() {
            return list.get(current++).val;
        }
    }
    

Log in to reply
 

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