leetcode 第331题：验证二叉树的前序序列化
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
示例:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true 解题方法
栈参照题解
解题思路由于字符串preorder中每个字符以逗号分隔，先将preorder分割为数组
创建栈stack来存储每个节点处占位的数量，因为根节点自身需要占位，所以初始压栈1
获取preorder的长度n，在[0,n)的范围内循环得到当前节点preorder[i]
在当前节点下，有左右两个子节点
若遇到一个空节点，需要用#占位(栈顶元素减1)
若遇到一个非空节点，除了它本身需要占位(栈顶元素减1)，还需要对它的左右两个子节点用#占位(压栈2)无论何时，如果无需占位(栈顶元素变为0)，就无需压栈
最终返回栈stack是否为空，为空表示二叉树的前序序列化正确
时间复杂度：O(n)，n为二叉树的节点数
空间复杂度：O(n)
python3
class Solution: def isValidSerialization(self, preorder: str) -> bool: preorder = preorder.split(",") n = len(preorder) stack = [1] i = 0 while i<n: if not stack: return False if preorder[i]=="#": top = stack.pop()-1 if top>0: stack.append(top) i += 1 else: top = stack.pop()-1 if top>0: stack.append(top) stack.append(2) i += 1 return not stackphp
class Solution { function isValidSerialization($preorder) { $preorder = explode(",",$preorder); $n = count($preorder); $stack = [1]; $i = 0; while($i<$n){ if(empty($stack)){ return false; } if($preorder[$i]=="#"){ $top = array_pop($stack)-1; if($top>0){ array_push($stack,$top); } $i++; }else{ $top = array_pop($stack)-1; if($top>0){ array_push($stack,$top); } array_push($stack,2); $i++; } } return empty($stack); }}