C++, 3ms O(1) space O(n) time with stringstream;


  • 0
    D

    A tree with one value has 1 non null node and 2 null nodes. Whenever you add a node, you replace a null node with a non null node, then you add two null nodes to your new node, for a net difference between non null and null nodes per node insertion is 0.

    The tree with one value had 1 more null than non null, so any valid tree must also have 1 more null than non null. Additionally, the final node of the pre order must be null no matter what. If it isn't then that means there are more nodes, which means its not the final node. This means that before reaching the final node, there must always be equal amounts of non nulls and nulls.

    If we consider adding a non null node to be +1 and adding a non null to be -1, the final tree must have a balance of -1. Because non null nodes are added before the null nodes are, the balance of the tree should never go negative until the final node is reached.

    This code uses stringstream to iterate through the values and continuously adds to the balance of the tree. If the balance goes negative, it breaks and returns true only if the end of the serialization was reached. It also returns false if the balance is not -1 even if the end of the serialization was reached.

    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            int bal = 0;
            stringstream ss(preorder);
            string val;
            while(getline(ss,val,',')){
                bal += val == "#" ? -1 : 1;
                if (bal < 0) break;
            }
            string check;
            return bal == -1 && !(bool)getline(ss,check,',');
        }
    };
    

Log in to reply
 

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