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


class Solution2(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        cnt = 1
        for node in preorder.split(','):
            if cnt == 0:
                return False
            elif node == '#':
                cnt -= 1
            else:
                cnt += 1
        return cnt == 0


class Solution3(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        count_to_visit = 1
        for c in preorder.split(','):
            count_to_visit -= 1
            if count_to_visit < 0:
                return False
            if c != '#':
                count_to_visit += 2
        return count_to_visit == 0


if __name__ == "__main__":
    s = Solution()

    preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
    assert s.isValidSerialization(preorder) is True

    preorder = "1,#"
    assert s.isValidSerialization(preorder) is False

    preorder = "9,#,#,1"
    assert s.isValidSerialization(preorder) is False

    preorder = "1,#,#,#,#"
    assert s.isValidSerialization(preorder) is False

    preorder = "9,#,92,#,#"
    assert s.isValidSerialization(preorder) is True