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

  • 0

    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 {
        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) );
                while( pos<L-2 && preorder[pos]=='#' ){ // leaf node
                    if( hasRight.empty() )
                        return false;
                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.