My Java Solution


  • 0
    G
    public class BSTIterator {
        Stack<TreeNode> stack;
        Set<TreeNode> visited;
    
        public BSTIterator(TreeNode root) {
            stack = new Stack<>();
            visited = new HashSet<>();
            if (root != null) {
                stack.push(root);
            }
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty();
        }
    
        //leftmost element in the right subtree
        /** @return the next smallest number */
        public int next() {
            while (true) {
                TreeNode temp = stack.pop();
                if (visited.contains(temp)) {
                    return temp.val;
                }
            
                if (temp.right != null) {
                    stack.push(temp.right);
                }
                stack.push(temp);
                if (temp.left != null) {
                    stack.push(temp.left);
                }
                visited.add(temp);
            }
        }
    }

Log in to reply
 

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