My 4ms C++ solution, beats 73.42% of cppsubmissions.


  • 0
    C

    The main conception of my code is to construct a stack that stores the node that still have the right child to visit. While one a '#' is visited, the top node of the stack can be popped up.

    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            int L = preorder.length();
            if( L==0 )
                return true;
            if( preorder[0]=='#' )
                return L==1;
            if( L==1 || preorder[L-1]!='#' || preorder[L-2]!=',' )
                return false;
            stack<string> hasRight;
            int pos = preorder.find_first_of(',');
            int prePos=0;
            if( pos==string::npos || pos==L-2 )
                return false;
            while( pos!= L-2 ){
                hasRight.push( preorder.substr(prePos,pos-prePos) );
    			pos++;
                while( pos<L-2 && preorder[pos]=='#' ){ // leaf node
                    if( hasRight.empty() )
                        return false;
                    hasRight.pop();
                    pos+=2;
                }
                if( pos>=L-2 )
                    return hasRight.empty();
                prePos = pos;
                pos = preorder.find_first_of( ',', prePos );
                
            }
            return (pos==L-2 && hasRight.empty());
        }
    };

Log in to reply
 

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