3ms c++ with O(1) space and O(n) time


  • 2

    The idea is simple: 1) Every node/null must have a parent except the root. 2) As a binary tree, the number of nulls must be one plus the number of nodes.
    As long as we meet a node/null we increment/decrement cnt. When we meet a new node/null we check if cnt already becomes zero (which means the tree has already been full before). When we are done with all nodes/nulls we also check if cnt has become zero which otherwise means the tree is not complete yet.

    bool isValidSerialization(string preorder) {
        int cnt = 1;
        bool lastd = false;
        for (char c : preorder) {
            if (isdigit(c)) {
                if (lastd)
                    continue;
                if (!cnt)
                    return false;
                cnt++;
                lastd = true;
            }
            else {
                if (c == '#')
                    cnt--;
                lastd = false;
            }
        }
        return cnt == 0;
    }
    

  • 0
    J

    Good solution!


Log in to reply
 

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