Java ArrayList solution


  • 1
    C
    public class BSTIterator {
    TreeNode root;
    ArrayList<Integer> ls = new ArrayList<Integer>();
    int point = 0;
    int n = 0;
    
    public BSTIterator(TreeNode root) {
        this.root = root;
        inorder(root);
        n = ls.size();
    }
    
    private void inorder(TreeNode root) {
        if(root == null) return;
        if(root.left != null) inorder(root.left);
        ls.add(root.val);
        if(root.right != null) inorder(root.right);
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(point < n) return true;
        else return false;
    }
    
    /** @return the next smallest number */
    public int next() {
        return ls.get(point++);
    }
    

    }

    1. use inorder to traverse the tree and save in ArrayList when initiate iterator
    2. hasNext() means check whether point in the size of list
      next() means move point in list

    I guess moving point in list is quicker than pop() in stack.


  • 0

    You are using more than O(h) memory


Log in to reply
 

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