java solution without stack, both O(1).


  • 0
    C
    public class BSTIterator {
        List<Integer> order = new ArrayList<>();
        int pointer = 0;
    
        public BSTIterator(TreeNode root) {
            parseBST(root);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return ++pointer < order.size() + 1;
        }
    
        /** @return the next smallest number */
        public int next() {
          return  order.get(pointer - 1);
        }
        
        private void parseBST(TreeNode root) {
            if(root == null) return;
            if(root.left != null) parseBST(root.left);
            order.add(root.val);
            if(root.right != null) parseBST(root.right);
        }
    }
    
    ``

Log in to reply
 

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