Straight-forward C++ solution with explanation
The idea is simple.\n\nDenote the number of null nodes as nullCnt, the number of actual nodes as nodeCnt.\n\nFor a binary tree, the number of null nodes is alwa
The idea is simple.\n\nDenote the number of null nodes as `nullCnt`, the number of actual nodes as `nodeCnt`.\n\nFor a binary tree, the number of null nodes is always the number of actual nodes plus 1. `nullCnt==nodeCnt+1`;\n\nSo,\n\n 1. if `nullCnt>nodeCnt+1`, the tree is invalid.\n 2. if `nullCnt<nodeCnt+1`, the tree is incomplete.\n 3. if `nullCnt==nodeCnt+1`, the tree is complete and can't be extended.\n\nWe just need to keep track of `nullCnt` and `nodeCnt` as we go through the sequence and check these conditions above.\n\nActually, recording `nullCnt-nodeCnt` is enough, so you can further improve the code.\n\n    class Solution {\n    public:\n        bool isValidSerialization(string preorder) {\n            int nodeCnt=0,nullCnt=0;\n            vector<string> v=splitStr(preorder,',');\n            for(int i = 0; i<v.size(); i++){\n                if(v[i]=="#") ++nullCnt;\n                else ++nodeCnt;\n                if(nullCnt>=nodeCnt+1 && i!=v.size()-1) return false;\n            }\n            return nullCnt==nodeCnt+1;\n        }\n        \n        vector<string> splitStr(string str, char delimiter){\n        \tvector<string> r;\n        \tstring tmpstr;\n        \twhile (!str.empty()){\n        \t\tint ind = str.find_first_of(delimiter);\n        \t\tif (ind == -1){\n        \t\t\tr.push_back(str);\n        \t\t\tstr.clear();\n        \t\t}\n        \t\telse{\n        \t\t\tr.push_back(str.substr(0, ind));\n        \t\t\tstr = str.substr(ind + 1, str.size() - ind - 1);\n        \t\t}\n        \t}\n        \treturn r;\n        }\n    };\n\n\n\n**Edit:**\nThe algorithm scans the string **one node at a time from the beginning**, once it finds `nullCnt>nodeCnt+1`, it stops and return false. \n\nIf it finds `nullCnt==nodeCnt+1`, that means by now, the tree is valid(otherwise the algorithm would return false before this) and complete, if there are more nodes to come, it returns false; if it's the last node, the algorithm returns true. \n\nIf it finds `nullCnt<nodeCnt+1`, that means the tree is incomplete but not invalid(or the algorithm would return false before this) by now, if this is the last node and no more nodes comes after it, the tree is invalid.\n\nExample:\n\n` "#,1,#"`\t1st node is `#`, `nullCnt==1`, `nodeCnt==0`, `nullCnt==nodeCnt+1`, the tree is complete by now, but there are more nodes after it, so it's invalid.\n\n` "1, #"`\t1st node is `1`, `nullCnt==0`, `nodeCnt==1`, `nullCnt<nodeCnt+1`, the tree is incomplete, but there are more nodes after it, so we proceed, 2nd node is `#`, `nullCnt==1`, `nodeCnt==1`, `nullCnt<nodeCnt+1`, the tree is incomplete and there are no more nodes left, so it's invalid.\n\n**Edit2:**\n\nWhy for a binary tree, `nullCnt==nodeCnt+1`?\n\nFor an empty binary tree, `nullCnt=1`, `nodeCnt=0`, `nullCnt==nodeCnt+1`.\n\nEach time we add an actual node, we take the place of one null node and create two null nodes, so the net gain of null node is one, which is also the net gain of actual node. Thus, the actual nodes and null nodes will increase by the same amount, which means `nullCnt==nodeCnt+1` will always hold.
[]