Simple 4ms C++ solution by simulating the pre-order search without using a stack


  • 0
    W
    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            stringstream ss(preorder);
            string token;
            int hasRight = 0; // count the number of nodes whose right nodes has not been searched yet.
            bool hasNext;
            while(true) {
                if (!getline(ss, token, ','))
                    return false;
                
                while (token != "#") {
                    hasRight ++;
                    if (!getline(ss, token, ','))
                        break;
                }
                
                if (hasRight == 0)
                    return !getline(ss, token, ',');
                hasRight--;
            }
            
        }
    };

Log in to reply
 

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