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