Short C++ code with explanations (single pass, no tockenize, no stack, no recursion)

  • 0

    There is not any totally new idea regarding the algorithm in the code below. I just thought that it might be helpful to mention a truly single-pass and easy to understand C++ code with a bit different explanation.

    If you start with the shortest possible valid input string ("#"), you clearly see that you have 0 non-null nodes and 1 null node. Every time you want to add a new non-null node to the tree, you need to add two more null nodes (e.g. "1##", "12###" and "1#2##"). So there must always be exactly one more null node in the whole tree. If you start with a simple counter and scan the input string from left to right by incrementing the counter for every non-null node and decrementing it for every null node, it can be proven (by induction) that:

    • the input string is valid if and only if the counter is equal to -1 at the end,
    • if the counter gets negative before reaching the end, the input string is not valid,
    • if the counter gets zero, it means you're done with traversing a left subtree.
    bool isValidSerialization(std::string preorder) {
        preorder.push_back(','); // no harm as we know the input string is in the correct format
        int i = 0, cnt = 0; // increment 'cnt' for each non-null node & decrement for each null (#) node
        while (i < preorder.length() && cnt > -1) {
            if (preorder[i] == '#') { cnt--; i += 2; } // skip the next ',' in the input
            else if (std::isdigit(preorder[i])) { i++; } // continue until reaching the end of digits of the non-null node
            else if (preorder[i] == ',') { cnt++; i++; } // the last node can't be a null node, so increment the counter
            else { return false; } // a wrong character in the input string
        return cnt == -1 && i >= preorder.length();

Log in to reply

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