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

# Code

Java

• import java.util.Stack;

public class Verify_Preorder_Serialization_of_a_Binary_Tree {

// https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution
public class Solution_noStack {
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int diff = 1; // if single node tree [root]
for (String node: nodes) {
if (--diff < 0) return false;
if (!node.equals("#")) diff += 2;
}
return diff == 0;
}
}

public class Solution {
public boolean isValidSerialization(String preorder) {
if (preorder == null || preorder.length() == 0) {
return true;
}

String[] nodes = preorder.split(",");
Stack<String> stack = new Stack<>();

for (String node : nodes) {
if (node.equals("#")) {
// after first while loop, current node can be deemed as #
while (!stack.isEmpty() && stack.peek().equals("#")) {
stack.pop(); // pop # in stack
if (stack.isEmpty()) { // should leave a number in stack
return false;
}

stack.pop(); // pop val with left-# and right-#   =>   repalce it with #
}
}

stack.push(node);
}

return stack.size() == 1 && stack.peek().equals("#");
}
}
}

• Todo

• class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
p = preorder.split(",")
if len(p) == 1:
if p[0] == "#":
return True
return False
stack = [p[0]]
for c in p[1:]:
if len(stack) == 1 and stack[0] == "#":
return False
stack.append(c)
while len(stack) > 2 and stack[-1] + stack[-2] == "##":
stack.pop()
stack.pop()
stack.pop()
stack.append("#")
if len(stack) == 1 and stack[0] == "#":
return True
return False