C++ Stack Solution


  • 0
    M
     #include <stack>
     using namespace std;
    class BSTIterator {
    public:
        bool hasRoot;
        stack<TreeNode*> st;
        BSTIterator(TreeNode *root) {
            if( root == NULL) hasRoot = false;
            else hasRoot = true;
            TreeNode *cur = root;
            while( cur != NULL){
                st.push(cur);
                cur = cur->left;
            }
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            if(!hasRoot) return false;
            if(!st.empty()) return true;
            return false;
        }
    
        /** @return the next smallest number */
        int next() {
            if( !st.empty() && st.top() != NULL){
                TreeNode *cur = st.top();
                st.pop();
                if(cur->right != NULL){
                    TreeNode* right = cur->right;
                    while(right != NULL){
                        st.push(right);
                        right = right->left;
                    }
                }
                return cur->val;
            }
            return 0;
        }
    };

Log in to reply
 

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