# Verify binary tree presequence serialization (331)

Posted on Dec. 2, 2022, 6:23 p.m. by 楊雅文

Category:
The front end
Tag:
javascript
algorithm
leetcode
## Verify preorder serialization of binary trees

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-empty node, we can record the value of that node. If it is an empty node, we can use a token value record, such as #

## The problem solving code

Idea: We can reduce a legal sequence layer by layer. Ex. :

- "9 and 4, #, # 1, #, #, 2 #, 6, #, #" 4 # # is a legitimate preorder traversal results, the directly down to #, in turn
- "9 and 4, #, # 1, #, #, 2 #, 6, #, #"
- "1, 3, 9 #, #, #, and 2, #, 6, #, #"
- "2, 3, 9 #, #, #, 6, #, #"
- "9, # 2, # 6, #, #"
- "9, # 2, #, #"
- "#, 9 #,"
- In this way, all the sequences are reduced to determine whether there is only one root node

```
var isValidSerialization = function(preorder) {
let stack = []; // Store the deleted node
let orderS = preorder.split(",");
for (let i = 0; i orderS.length; i++) {
const order = orderS[i];
stack.push(order); // Push the stack in turn
// console.log("stack",stack);
while (stack.length = 3 (stack[stack.length - 1= = ="#" stack[stack.length - 2= = ="#")) {
// reduce point, change the value of n## combination to #
stack[stack.length - 3] = "#";
stack.pop();
stack.pop();
}
// console.log("stack POP",stack);
const last = stack.length - 1;
if (stack.length === 2 stack[last]=== "#" stack[last - 1= = ="#") return false; // Determine the boundary condition, if the reduced stack is # #, then the next push element may also be #, and # # # is an invalid sequence
}
return stack.length === 1 stack[0= = ="#";
};
Copy the code
```