1. Title Description

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

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”.

Second, train of thought analysis

Let’s start with the problem. If we walk through the nodes in order, each node will have a corresponding representation (either # or a number), and in order, each child node will extend from the parent node.

That whether we can think so, each node is created, wasted his father components of a value, derived the two child nodes, we can define a stack, initialized to [1], when a node, the parent node minus 1 (stack was the last value minus 1), if the value for value, add two child node 2 (2) stack in the new, if is empty, If the value in the stack is 0, the node is full and deleted. Finally, if the stack is empty, it indicates that the stack is the correct sequential serialization of the binary tree.

calculus

Preorde [I] -- > the parent node minus 1-2 - - > > add two child node stack the value of 9 -- -- > 1-1 - - > push (2) -- - > stack = [2] -- > 3-2-1 - > push (2) - > stack = 4 - [1, 2] - > 2-1 - > push (2) - > stack =,1,2 [1] # 1 - - - - > 2 - > - > stack = #,1,1 [1] -- > 1-1 (0 delete) -- -- > > stack = [1, 1] 1 - > 1-1 (0 delete) - > push (2) -- - > stack = [1, 2] # 1 - - - - > 2 - > - > stack = [1, 1] # 1-1 - > (0 delete) -- -- > > stack = [1] · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · etc · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·Copy the code

AC code

var isValidSerialization = function(preorder) { const n = preorder.length let stack = [1] let i = 0 while (i<n){ if(! stack.length){ return false } if(preorder[i]===','){ ++i }else if(preorder[i]==='#'){ stack[stack.length - 1]--; if(stack[stack.length - 1]===0){ stack.pop() } ++i; }else{ while(i<n && preorder[i]! ==','){ ++i; } stack[stack.length-1]--; if(stack[stack.length - 1]===0){ stack.pop() } stack.push(2); } } return stack.length === 0; };Copy the code

Four,

Recently, we found that all the problems are solved by stack method, which shows the importance of stack application in algorithm.