3ms c++ with O(1) space and O(n) time
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.\nAs lo
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.\nAs 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.\n```\nbool isValidSerialization(string preorder) {\n    int cnt = 1;\n    bool lastd = false;\n    for (char c : preorder) {\n        if (isdigit(c)) {\n            if (lastd)\n                continue;\n            if (!cnt)\n                return false;\n            cnt++;\n            lastd = true;\n        }\n        else {\n            if (c == '#')\n                cnt--;\n            lastd = false;\n        }\n    }\n    return cnt == 0;\n}\n```
[]