My C++ Postorder Iterator Solution using Stack


  • 0
    J

    I think it is good to post it here for discussion.

    class BSTIterator {
    private:
        stack<TreeNode*> stk;
        TreeNode* lastVisitedNode;
    public:
        BSTIterator(TreeNode *root) {
            if(root == NULL)
                return;
            lastVisitedNode=NULL;
            
            pushAllNodes(root);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !stk.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode* nxt=stk.top();
            stk.pop();
            lastVisitedNode=nxt;
            pushAllNodes(NULL);
            return nxt->val;
        }
        
        void pushAllNodes(TreeNode * node)
        {
            while(!stk.empty() || node != NULL)
            {
                if(node != NULL)
                {
                    stk.push(node);
                    node=node->left;
                }
                else
                {
                    TreeNode* peek=stk.top();
                    if(peek->right != NULL && peek->right != lastVisitedNode)
                    {
                        node=peek->right;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
    };
    

Log in to reply
 

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