Verify Preorder Serialization of a Binary Tree

Problem: Verify Preorder Serialization of a Binary Tree

The general idea is when we get left subtree and right subtree verified, we mark the root node verified and pop it from the stack. We use such a trick that every time we push a number into the stack, we push one more symbol into it. So that when we get left subtree verified, we first pop the redundant symbol. After we verified the right subtree, we keep popping numbers until we pop a redundant symbol, which means we verified a left subtree and need to wait for right subtree to be verified.

Take "9,3,4,#,#,1,#,#,2,#,6,#,#" as an example, we first push 9,l,3,l,4,l into the stack. When we see the first "#", we pop "l" because of a verified left subtree thus the stack becomes 9,l,3,l,4. When we get the second "#", the right subtree of 4 is also verified thus 4 is popped. Then we keep popping and find a "l" symbol, which means 4 is the left child of its parent so we stop popping and try to verify a right subtree. At this time, the stack is 9,l,3, waiting for the right subtree of 3 to be verified.

Code in Python:

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        stack = ["l"]
        _preorder = preorder.split(',')
        for element in _preorder:
            if element != "#": stack += [element, "l"]
            else:
                if not stack: return False
                while stack.pop() != "l":
                    if not stack: return False
        return not stack