c++ stack solution easy to understand


  • 0
    Q
    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            int len = preorder.size();
            if(len == 0)
                return true;
            stack<char> s;
            int i=0;
            while(i<len && isdigit(preorder[i]))
                i++;
            i++;
        
            s.push(preorder[0]);
            if(len == 1)
                return preorder[0] == '#';
            
            for(;i<len;i+=2){
                int cur = i;
                char ch = preorder[i];
                if(ch == '#'){
                    if(s.top() != '#')
                        s.push('#');
                    else{
                        if(!s.empty()){
                            s.pop();
                            if(s.empty())
                                return false;
                            s.pop();
                            s.push('#');
                        }
                    }
                }
                else{
                    if(s.empty())
                        return false;
                    while(i<len && isdigit(preorder[i]))
                        i++;
                    i--;
                    s.push(ch);
                }
                while(s.size() >= 2 && s.top() == '#'){
                    s.pop();
                    if(s.top() == '#'){
                        s.pop();
                        if(s.empty())
                            return false;
                        s.pop();
                        s.push('#');
                    }
                    else{
                        s.push('#');
                        break;
                    }
                }    
            }
            return s.size() == 1;
        }
    };
    

Log in to reply
 

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