题目：验证二叉树的前序序列化

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 #代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如"1,,3"。

示例 1:

输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

示例 2:

输入: "1,#"
输出: false

示例 3:

输入: "9,#,#,1"
输出: false

来源：力扣（LeetCode）第331题

链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree

分析：

就是每个爸爸都要找到两个儿子。(两个儿子可以是数字也可以是#)
#爸爸什么都没有，比较惨。
上面两条任意一条不对都不合法。

思路:

前序遍历严格遵守中，左，右的顺序。
所以第一个为根节点，到第一个#为止，前面这些数字都是根节点的最左边的左子节点
维护一个栈stack，栈中存的是未确认它是否有两个子节点的节点，就是说如果该节点找到了他的两个子节点，就出栈(#也算它的子节点)。
凡是找到数字，全都入栈，因为一开始找到数字，你只能确认它的左子节点是下一个值(数字或#)，无法知道它的右子节点。
当找到第一个#时，开始遍历右子节点。因为没有左子节点了，遍历最近的节点的右子节点，也就是栈顶元素！！！
一旦遍历了右子节点，那么该节点的左右子节点都找到了，出栈。
接下来继续重复之前的规律，如果字符串合法，那么stack中的元素都被弹出去了，如果栈中还有元素，那么就说明有的元素找不到它的两个儿子。
大概是这么个思路，不过还有些细节要处理。

看我写的代码：

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        if preorder == '':
            return False
        if preorder == '#':
            return True
        pol = preorder.split(',')  # PreOrderList
        stack = []  # 只有数字入栈，当确认了该数字的两个子节点后出栈
        n = len(pol)
        isLeftTree = True  # 如果现在遍历的是左子树的话，不用出栈，如果为右子树的话无论是什么都要出栈
        for i in range(n):
            if pol[i].isdigit():
                if not isLeftTree:
                    if not stack:  # 如果栈是空的还要弹元素的话说明这字符串不合法。
                        return False
                    stack.pop()
                stack.append(pol[i])  # 无论是左子树还是右子树，遇到数字都要入栈
                isLeftTree = True  # 如果遍历到的是数字的话，那么又开始遍历左子树了。
            else:
                isLeftTree = False  # 当左子树遍历到#号时那么左子树完了，开始遍历右子树。
                if pol[i - 1] == '#':
                    if not stack:
                        return False
                    stack.pop()
        return len(stack) == 0  # 栈为空就说明合法，每一个节点都找到了它的两个子节点了。

复杂度分析：

时间复杂度：O(n) n为pol列表长度
空间复杂度：O(n)

总结：

写的不是最优，总的来说就是将数据分为遍历左子树和右子树两种情况。