Leetcode Verify Preorder Serialization of a Binary Tree problem solution

In this Leetcode Verify Preorder Serialization of a Binary Tree problem solution, One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as '#'. For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.

Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree. It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.

Problem solution in Python.

```class Solution:
def isValidSerialization(self, preorder: str) -> bool:
preorderList = preorder.split(',')
if len(preorderList)%2 != 1:
return False
stack = []
for node in preorderList:
stack.append(node)
while len(stack) >= 3 and stack[-2] == stack[-1] == '#' and stack[-3] != '#':
for i in range(3):
stack.pop()
stack.append('#')
return len(stack) == 1 and stack[0] == '#'
```

Problem solution in Java.

```public boolean isValidSerialization(String preorder) {

if(preorder.length()==1 && preorder.charAt(0)=='#'){
return true;
}

Deque<Boolean> stackObj = new ArrayDeque<Boolean>();

String[] nodes= preorder.split(",");

for(int i=0;i<nodes.length;i++){

if(nodes[i].equals("#")){

if(stackObj.isEmpty()){
return false;
}else{

while(!stackObj.isEmpty() && stackObj.getFirst()){
stackObj.removeFirst();
}

if(!stackObj.isEmpty()){
stackObj.removeFirst();
}else if(i+1<nodes.length){
return false;
}
}
}else{
}
}

if(stackObj.isEmpty()){
return true;
}

return false;[]
}
```

Problem solution in C++.

```class Solution {
public:
bool isValidSerialization(string preorder) {
int internalNode = 0, externalNode = 0;
char inString[preorder.length() + 1];
strcpy(inString, preorder.c_str());
char *nodeValue = strtok(inString, ",");
while (nodeValue) {
if (nodeValue[0] == '#') ++externalNode;
else ++internalNode;
nodeValue = strtok(NULL, ",");
if (externalNode == internalNode + 1) {
if (nodeValue) return false;
return true;
}
}
return false;
}
};
```

Problem solution in C.

```char *checkTree(char *start) {
if (*start == 0) return 0;
if (*start == '#') return start + 1;
char *next = start + 1;
next = checkTree(next);
if (next == 0) return 0;
next = checkTree(next);
if (next == 0) return 0;
return next;
}

bool isValidSerialization(char * preorder){
char *c; int i;
for (c = preorder, i = 0; *c; c++) {
if (*c == ',') { i++; continue; }
if (*c != '#') { preorder[i] = 'X'; continue; }
preorder[i] = '#';
}
preorder[i+1] = 0;

char *end = checkTree(preorder);
if (end == 0) return false;
if (*end != 0) return false;
return true;
}
```