My accepted solution, using stack, next() is O(1), hasNext() is O(h)


  • 0
    R
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    public class BSTIterator {
        
        private Stack<TreeNode> stack;
        private TreeNode preNode;
    
        public BSTIterator(TreeNode root) {
            preNode = root;
            stack = new Stack<>();
            stack.addAll(findMostLeftChain(root));
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            if (stack.isEmpty()){
                return false;
            }
            preNode = stack.pop();
            stack.addAll(findMostLeftChain(preNode.right));
            return true;
        }
    
        /** @return the next smallest number */
        public int next() {
            return preNode.val;
        }
        
        private Stack<TreeNode> findMostLeftChain(TreeNode node) {
            Stack<TreeNode> result = new Stack<>();
            while (node != null) {
                result.push(node);
                node = node.left;
            }
            return result;
        }
    }
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = new BSTIterator(root);
     * while (i.hasNext()) v[f()] = i.next();
     */

  • 0
    N
    This post is deleted!

  • 0
    L

    Although the code is accepted, I think your hasNext function has side-effect. The function is a judgement, your code can not be called twice or more in one place. Maybe you will be challenged in the real interview. Have fun


Log in to reply
 

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