The idea is simple.

Denote the number of null nodes as `nullCnt`

, the number of actual nodes as `nodeCnt`

.

For a binary tree, the number of null nodes is always the number of actual nodes plus 1. `nullCnt==nodeCnt+1`

;

So,

- if
`nullCnt>nodeCnt+1`

, the tree is invalid. - if
`nullCnt<nodeCnt+1`

, the tree is incomplete. - if
`nullCnt==nodeCnt+1`

, the tree is complete and can't be extended.

We just need to keep track of `nullCnt`

and `nodeCnt`

as we go through the sequence and check these conditions above.

Actually, recording `nullCnt-nodeCnt`

is enough, so you can further improve the code.

```
class Solution {
public:
bool isValidSerialization(string preorder) {
int nodeCnt=0,nullCnt=0;
vector<string> v=splitStr(preorder,',');
for(int i = 0; i<v.size(); i++){
if(v[i]=="#") ++nullCnt;
else ++nodeCnt;
if(nullCnt>=nodeCnt+1 && i!=v.size()-1) return false;
}
return nullCnt==nodeCnt+1;
}
vector<string> splitStr(string str, char delimiter){
vector<string> r;
string tmpstr;
while (!str.empty()){
int ind = str.find_first_of(delimiter);
if (ind == -1){
r.push_back(str);
str.clear();
}
else{
r.push_back(str.substr(0, ind));
str = str.substr(ind + 1, str.size() - ind - 1);
}
}
return r;
}
};
```

**Edit:**

The algorithm scans the string **one node at a time from the beginning**, once it finds `nullCnt>nodeCnt+1`

, it stops and return false.

If 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.

If 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.

Example:

`"#,1,#"`

1st 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.

`"1, #"`

1st 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.

**Edit2:**

Why for a binary tree, `nullCnt==nodeCnt+1`

?

For an empty binary tree, `nullCnt=1`

, `nodeCnt=0`

, `nullCnt==nodeCnt+1`

.

Each 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.