原题
先序遍历是序列化二叉树的方式之一。当遇到非空节点时，记录节点的值。如果是空节点，我们将其记为#。
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
例如，题目描述中的样例二叉树可以序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中#代表空节点。
给定一个逗号分隔值字符串，校验其是否是一个正确的二叉树先序遍历序列化字符串。设计一个不需要重建树的算法。
每一个逗号分隔值字符串中的值或者是整数，或者是字符'#'，代表空节点。
你可以假设输入格式总是有效的，例如，不可能出现两个连续的逗号，比如"1,,3"。
例1：
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
例2：
"1,#"
Return false
例3：
"9,#,#,1"
Return false
解题思路
- 方法一：利用Stack, 把序列化的结果不断压入栈，但栈内元素大于等于3的时候，如果遇到x # # => #，此过程相当于在逐步砍掉叶节点，过程如下
8 8 #
/ \ / \
9 # => # # =>
/ \
# #
- 方法二：统计树的出度（out-degree）和入度（in-degree）
- 根节点提供2个出度和0个入度（但初始时diff=1）
- 所有的非空节点提供2个出度和1个入度
- 所有的空节点但提供0个出度和1个入度
- 当遍历节点时，每次diff - 1（因为节点提供了一个入度）。
- 如果节点非#，diff + 2（因为非空节点提供了2个出度）
- 如果序列化是正确的，那么diff在任何时刻都不会小于0，并且最终结果等于0
完整代码
# method 1
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
stack = []
for node in preorder.split(","):
stack.append(node)
while len(stack) >= 3 and stack[-1] == stack[-2] == "#" and stack[-3] != "#":
stack = stack[:-3] +['#']
return len(stack) == 1 and stack[-1] == "#"
# method 2
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
diff = 1
for node in preorder.split(","):
diff -= 1
if diff < 0:
return False
if node != "#":
diff += 2
if diff == 0:
return True
return False
