# Verify binary tree presequence serialization (331)

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

## 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. :

1. "9 and 4, #, # 1, #, #, 2 #, 6, #, #" 4 # # is a legitimate preorder traversal results, the directly down to #, in turn
2. "9 and 4, #, # 1, #, #, 2 #, 6, #, #"
3. "1, 3, 9 #, #, #, and 2, #, 6, #, #"
4. "2, 3, 9 #, #, #, 6, #, #"
5. "9, # 2, # 6, #, #"
6. "9, # 2, #, #"
7. "#, 9 #,"
8. 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``````
Search