Not use stack, beats 95.39% of java submissions


  • -2
    L

    public class BSTIterator {
    private TreeNode root;

    public BSTIterator(TreeNode root) {
        this.root = root;
    }
    
    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        return root != null;
    }
    
    /**
     * @return the next smallest number
     */
    public int next() {
        TreeNode node = root, preNode = null;
        if (node == null) {
            return -1;
        }
    
        while (node.left != null) {
            preNode = node;
            node = node.left;
        }
    
        int result = node.val;
    
        if (node == root && root.right == null) {
            root = null;
        } else {
            if (node.right != null) {
                if (preNode == null) {
                    root = node.right;
                } else {
                    preNode.left = node.right;
                }
            } else {
                if (preNode != null) {
                    preNode.left = null;
                }
            }
        }
    
        return result;
    }

Log in to reply
 

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