“This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

[topic address]

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

_9_ / / 2/3/4 1 # 6 / \ \ / \ \ # # # # # #Copy the code

For example, the binary tree can be serialized as string above “4, 9 #, # 1, #, #, 2 #, 6, #, #”, where # represents a blank nodes.

Given a comma-separated sequence, verify that it is the correct preserialization of the binary tree. Write a feasible algorithm without reconstructing the tree.

Each comma-separated character is either an integer or a ‘#’ representing a null pointer.

You can assume that the input format is always valid; for example, it will never contain two consecutive commas, such as “1, 3”.

Example 1:

Input: "9,3,4,#,#,1,#,#,2,#,6,#,#" output: trueCopy the code

Example 2:

Input: "1,#" Output: falseCopy the code

Example 3:

Input: "9,#,#,1" Output: falseCopy the code

First of all, let’s look at the binary tree given in the above question. It can be seen that there are two # below each leaf node, and vice versa. If there are two #, then the nodes above them must be leaf nodes

Corresponding to the binary tree given in the question, we can also find a rule, that is, we eliminate the # under each leaf node, and update the leaf node to #, so as to achieve the effect of closing the binary tree from the bottom up

If this operation can continue all the way to the root node, then the given preorder is properly serialized

Then how to use this law to solve the problem, the solution idea is as follows:

  1. Serialize the preorder of the input to a tree group
  2. Preserialization of input traversed from back to forward, when two are encountered#And the values in front of them are not#“, then delete two#, replace the previous value with#
  3. If the above operation can continue up to the root node, then only one is left#If yes, the presequence serialization is correct; otherwise, it is incorrect

The code is as follows:

Var isValidSerialization = function(preorder) {const arr = preorder.split(','); // update x,#,# to # for(let I = arr. Length -1; i>=2; i--){ if(arr[i]==='#'&&arr[i-1]==='#'&&arr[i-2]! =='#'){ arr[i-2] = '#' arr.pop(); arr.pop(); }} / / if the last remaining only a #, shows the correct return arr. Length = = = 1 && arr [0] = = = '#'};Copy the code

At this point we have completed the post-order traversal of leetcode-145-binary tree

If you have any questions or suggestions, please leave a comment!