331.Verify Preorder Serialization of a Binary Tree

Tags: [binary_tree], [preorder], [serialization], [trick]

Link: https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/\#/description

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

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:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Returntrue

Example 2:
"1,#"
Returnfalse

Example 3:
"9,#,#,1"
Returnfalse

Solution: Trick

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        if not preorder:
            return True

        nodes = preorder.split(',')

        # At beginning, there is one slot for containing the root.
        num_of_slots = 1
        for node in nodes:

            # If there is no slots (place) to the current node, 
            # which means the given preorder sequence is invalid.
            if not num_of_slots:
                return False

            # Each node itself will take a slot.
            num_of_slots -= 1

            # If the current node is not None, 
            # it should have two children (maybe both are None, 
            # but it's OK), so we add 2 slots (places) here.
            if node != '#':
                num_of_slots += 2

        return num_of_slots == 0

Revelation:

• We can dynamic dispatch the slots to the remaining part of the tree.

Note:

• Time complexity = O(n), n is the length of the given preorder string.