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 preorder traversal.
When we encounter a nonnull 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
@tagtree
Algorithm
 The number of digits is always one less than
#
 The last one must be
#
 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/verifypreorderserializationofabinarytree/discuss/78551/7linesEasyJavaSolution 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