Nice Comparison (and short Solution)


  • 10

    Compare this typical iterative inorder traversal

    1.    TreeNode visit = root;
          Stack<TreeNode> stack = new Stack();
    2.    while (visit != null || !stack.empty()) {
    3.        while (visit != null) {
                  stack.push(visit);
                  visit = visit.left;
              }
              TreeNode next = stack.pop();
              visit = next.right;
              doSomethingWith(next.val);
          }
    

    with what we're supposed to support here:

    1.    BSTIterator i = new BSTIterator(root);
    2.    while (i.hasNext())
    3.        doSomethingWith(i.next());
    

    You can see they already have the exact same structure:

    1. Some initialization.
    2. A while-loop with a condition that tells whether there is more.
    3. The loop body gets the next value and does something with it.

    So simply put the three parts of that iterative solution into our three iterator methods:

    public class BSTIterator {
    
        private TreeNode visit;
        private Stack<TreeNode> stack;
        
        public BSTIterator(TreeNode root) {
            visit = root;
            stack = new Stack();
        }
    
        public boolean hasNext() {
            return visit != null || !stack.empty();
        }
    
        public int next() {
            while (visit != null) {
                stack.push(visit);
                visit = visit.left;
            }
            TreeNode next = stack.pop();
            visit = next.right;
            return next.val;
        }
    }

  • 0

    @StefanPochmann Yeah, your explanation is quite the point.


  • 0

    A C++ version using stack always.

    class BSTIterator {
    private:    
        stack<TreeNode*> node_stack;
    public:
        BSTIterator(TreeNode *root) {
            while(root) 
            {
                node_stack.push(root);
                root = root->left;
            }
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !node_stack.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode *t = node_stack.top();
            node_stack.pop();
            int ret = t->val;
            t = t->right;
            while(t)
            {
                node_stack.push(t);
                t = t->left;
            }
            return ret;
        }
    };
    

Log in to reply
 

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