O(h) space, O(1) avg time, using List


  • 2
    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.

  • 0
    T

    Nice job, seems next() still takes O(h) time


Log in to reply
 

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