“This is the 17th day of my participation in the Gwen Challenge in November. For details: The last Gwen Challenge in 2021” 331. Verify the sequential serialization of the binary tree

The title

Not important, look at the train of thought

The stack

Enumerating all the characters, pushing the characters onto the stack. If there are two consecutive # s in the stack, pop up two # s and the last digit in the stack. Know the end; There is only one character in the stack, and the character # is the correct binary tree sequential serialization

To see if the image is clear, edit the code as follows:

var isValidSerialization = function (preorder) {
  const array = preorder.split(', ')
  const len = array.length;
  const stack = []
  for (let i = 0; i < len; i++) {
    stack.push(array[i])
    while(stack.length >=3  && stack[stack.length-1] === stack[stack.length-2] && stack[stack.length-1= = =The '#' && stack[stack.length-3]! = =The '#'){
      stack.pop();
      stack.pop();
      stack.pop();
      stack.push(The '#')}}return stack.length === 1 && stack.pop() === The '#'
}
Copy the code

Out and in

Observe the degree of entry and exit in the figure below;

Degree of entry: the number of points to nodes

Output: the number of points a node points to

Observing the figure above, we can get 1. No matter what node, the degree of entry is 1. 2. The exit degree of all non-# nodes is 2, and the exit degree of # nodes is 0; 3, complete binary tree number of degrees === number of degrees

Based on the data and conclusions observed above, edit the code below

var isValidSerialization = function (preorder) {
  const array = preorder.split(', ')
  const len = array.length
  let diff = 1
  for (let i = 0; i < len; i++) {
    diff -= 1
    if (diff < 0) return false
    if(array[i] ! = =The '#') {
      diff += 2}}return diff === 0
}
Copy the code