[fun] summary of 3 different C++ solutions
method 1 \n\nThe first solution is inspired from the idea that we can delete the leaf node level by level .....\n\nWe need first implement the split function fo
**method 1** \n\nThe first solution is inspired from the idea that we can delete the leaf node level by level .....\n\nWe need first implement the split function for the latter calling ....\n\n             vector<string> split(string input, char delimiter){\n                vector<string> result;\n                string str=input;\n                while(!str.empty()){\n                    int ind=str.find_first_of(delimiter);\n                    if(ind==-1){\n                        result.push_back(str);\n                        str.clear();\n                    }\n                    else{\n                        result.push_back(str.substr(0, ind));\n                        str=str.substr(ind+1);\n                    }\n                }\n                return result;\n            }\n\nBased the split function , we need first split the string to a string array .\n\nBy using a bool array to mimic the process of deleting the leaf node level by level .\n\n\n\n      class Solution {\n        public:\n            bool isValidSerialization(string preorder) {\n                /*** for a binary tree : count_null=count_node+1 **/\n                int count_null=0, count_node=0;\n                vector<string> nodes=split(preorder, ',');\n                vector<bool> stack(nodes.size(), false);\n                int end = 0;\n                for (auto node : nodes) {\n                    if (end == 1 && !stack[end-1])  return false;\n                    stack[end++] = !(node == "#");\n                    while (end >= 3 && stack[end - 3] && !stack[end - 2] && !stack[end - 1]) {\n                        stack[end - 3] = false;\n                        end -= 2;\n                    }\n                }\n                return end == 1 && !stack[0];\n            }\n        };\n\n**method 2**\n\nThis idea is based on the solution from @dietpepsi\n\nIn a binary tree, if we consider null as leaves, then\n\n      all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root\n      all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).\n\nSuppose we try to build this tree. During building, we record the difference between out degree and in degree \n\n              diff = outdegree - indegree. \n\nWhen the next node comes, we then decrease diff by 1, because the node provides an in degree.\n If the node is not null, we increase diff by2, because it provides two out degrees. \n\n         If a serialization is correct, diff should never be negative and diff will be zero when finished.\n\nHere is the AC implementation ...\n\n    class Solution {\n    public:\n        bool isValidSerialization(string preorder) {\n            /*** for a binary tree : count_null=count_node+1 **/\n            int count_null=0, count_node=0;\n            vector<string> nodes=split(preorder, ',');\n            int diff = 1;\n            for(auto node : nodes) {\n                diff--;\n                if(diff < 0)  return false;\n                if(node != "#")  diff += 2;\n            }\n            return diff == 0;\n        }\n\n\n**Update**\n\nHere is a small changed version based on the method2 , I think this is more easy to understand ...\n\n    bool isValidSerialization(string preorder) {\n        /*** for a binary tree : count_null=count_node+1 **/\n        int count_null=0, count_node=0;\n        vector<string> nodes=split(preorder, ',');\n        int diff = 0;\n        for (int i = 0; i < nodes.size(); i++) {\n            if (i == 0) {\n                if(nodes[i] != "#") {\n                    diff += 2;\n                }\n                continue;\n            }\n            diff--;\n            if(diff < 0)  return false;\n            if(nodes[i] != "#")  diff += 2;\n        }\n        return diff == 0;\n    }\n\n\n**method 3**\n\n  The solution is based on the intuition that , \n\n        # of leaves = # of nonleaves + 1\n\nWe should satisfy the above equation in all the process of the pre-order-traverse of the tree ....\n\n**we just need to find the shortest prefix of the serialization sequence satisfying the property above. If such prefix does not exist, then the serialization is definitely invalid; otherwise, the serialization is valid if and only if the prefix is the entire sequence.**\n\n     bool isValidSerialization(string preorder) {\n            /*** for a binary tree : count_null=count_node+1 **/\n            int count_null=0, count_node=0;\n            vector<string> nodes=split(preorder, ',');\n            \n            int i = 0;\n            for (i = 0; i < nodes.size() && count_null != count_node + 1; i++) {\n                if(nodes[i] == "#")  count_null++;\n                else  count_node++;\n            }\n            return i == nodes.size() && (count_null == count_node + 1);\n        }
[]