Easy C++ O(n) solution with comments. 3ms


  • 0
    M

    The thing that we know for sure is that if its a null node, we can't go any further, and null node is always a binary tree. So just validate that, and see if we manage to verify this property till end of string

    class Solution {
    public:
        bool validate(string &preorder, int &cur) {
           // Trim any leading commas
            while (cur < preorder.length() && preorder[cur] == ',') cur++;
    
           /* Reached end of string, we are good. */
            if (cur == preorder.length()) return true;
    
           /* Shouldn't reach to something more than length of string */
            if (cur > preorder.length()) return false;
    
           /* Null strings are binary tree */
            if (preorder[cur] == '#') {
                cur++;
                return true;
            }
            
           /* Skip over the actual non-null node */
            while (cur < preorder.length() && preorder[cur] != ',') cur++;        
            
            /* Are left and right childs ok ? */
            bool l = validate(preorder, cur);
            bool r = cur < preorder.length() && validate(preorder, cur);
    
            return l && r;
        }
        
        bool isValidSerialization(string preorder) {
            int s = 0;
            bool a = validate(preorder, s);
            return a && (s == preorder.length());
        }
    };
    

Log in to reply
 

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