Java O(1) space and O(1) time for next/hasNext beat 90%


  • 1
    A
    public class BSTIterator {
    
    private TreeNode current;
    
    public BSTIterator(TreeNode root) {
        TreeNode fake = new TreeNode(0);
        fake.right = root;
        TreeNode tail = fake;
        TreeNode rest = tail.right;
        while (rest != null) {
            if (rest.left == null) {
                tail = rest;
                rest = rest.right;
            } else {
                TreeNode tmp = rest.left;
                rest.left = tmp.right;
                tmp.right = rest;
                rest = tmp;
                tail.right = tmp;
            }
        }
        this.current = fake.right;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return current != null;
    }
    
    /** @return the next smallest number */
    public int next() {
        try {
          return current.val;
        } finally {
          current = current.right;
        }
    }
    

    }

    But it is destructive.
    Based on https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm


Log in to reply
 

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