My Java Solution O(n) memory: Does anyone have a O(log(n)) solution???


  • 0
    K
    Hello, 
    
    This code uses O(n) (number of elements in the list) memory and is still accepted.
    Does anyone has a O(log(n)) solution???
    
    public class BSTIterator {
        
        private Stack<Integer> values = new Stack<Integer>();
    
        public BSTIterator(TreeNode root) {
            visit(root);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !values.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            return values.pop();
        }
        
        /* Reverse in order list traversal. */
        private void visit(TreeNode cur) {
            if(cur == null)
                return;
            visit(cur.right);
            values.push(cur.val);
            visit(cur.left);
        }
    }

  • 0
    public class BSTIterator {
    	List<TreeNode> mins;
    	public BSTIterator(TreeNode root) {
    		mins = new ArrayList<TreeNode>();
    		while(root!=null) {
    			mins.add(root);
    			root=root.left;
    		}
    	}
    	/** @return whether we have a next smallest number */
    	public boolean hasNext() {
    		return (mins.size()>0)?true:false;
    	}
            /** @return the next smallest number */
    	public int next() {
    		TreeNode min = mins.remove(mins.size()-1);
    		TreeNode subright = min.right;
    		while(subright!=null) {
    			mins.add(subright);
    			subright = subright.left;
    		}
    		return min.val;
    	}
    }
    
    1. Constructor: initialize a List<TreeNode> and adds all the left children starting from root. At the end the list will have one TreeNode for each level.
    2. hasNext(): return true if the List<TreeNode> is not empty.
    3. next(): remove the last element of the mins List. If the removed TreeNode has a right subtree, add to the List of mins all the left children, again at most one TreeNode for each level.

Log in to reply
 

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