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)
                if (!cnt)
                    return false;
                lastd = true;
            else {
                if (c == '#')
                lastd = false;
        return cnt == 0;

  • 0

    Good solution!

Log in to reply

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