# Question

Formatted question description: https://leetcode.ca/all/331.html

 331	Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal.
When we encounter a non-null node, we record the node's value.
If it is a null node, we record using a sentinel value such as #.

_9_
/   \
3     2
/ \   / \
4   1  #  6
/ \ / \   / \
# # #  #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#",
where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree.
Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid,
for example it could never contain two consecutive commas such as "1,,3".

Example 1:

Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

Example 2:

Input: "1,#"
Output: false

Example 3:

Input: "9,#,#,1"
Output: false

@tag-tree


# Algorithm

1. The number of digits is always one less than #
2. The last one must be #
3. leaf node: number, #, #

If we initialize a counter to 0,

• When a number is encountered, the counter increases by 1,
• When the # sign is encountered, the counter is decreased by 1, Then the counter should still be 0 at the end.

Two examples that return False, #,7,6,9,#,#,# and 7,2,#,2,#,#,#,6,#, then through these two counter examples,

• If the root node is empty, there can be no more nodes behind,
• And there cannot be three consecutive # signs.

So when we add or subtract the counter, if we encounter the # number, and the counter is already 0, and then subtracted to become a negative number, we directly return False, because in the correct sequence, any position i is in [ 0, i] The number of # numbers in the range is not greater than the number of digits.

When the loop is complete, we check whether the counter is 0 and also see whether the last character is # sign.

Java