原題
先序遍歷是序列化二叉樹的方式之一份殿。當(dāng)遇到非空節(jié)點時玷室，記錄節(jié)點的值。如果是空節(jié)點篮幢，我們將其記為#大刊。
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
例如，題目描述中的樣例二叉樹可以序列化為字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"洲拇，其中#代表空節(jié)點奈揍。
給定一個逗號分隔值字符串，校驗其是否是一個正確的二叉樹先序遍歷序列化字符串赋续。設(shè)計一個不需要重建樹的算法男翰。
每一個逗號分隔值字符串中的值或者是整數(shù)，或者是字符'#'纽乱，代表空節(jié)點蛾绎。
你可以假設(shè)輸入格式總是有效的，例如鸦列，不可能出現(xiàn)兩個連續(xù)的逗號租冠，比如"1,,3"。
例1：
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
例2：
"1,#"
Return false
例3：
"9,#,#,1"
Return false
解題思路
- 方法一：利用Stack, 把序列化的結(jié)果不斷壓入棧薯嗤，但棧內(nèi)元素大于等于3的時候顽爹，如果遇到x # # => #，此過程相當(dāng)于在逐步砍掉葉節(jié)點骆姐，過程如下
8 8 #
/ \ / \
9 # => # # =>
/ \
# #
- 方法二：統(tǒng)計樹的出度（out-degree）和入度（in-degree）
- 根節(jié)點提供2個出度和0個入度（但初始時diff=1）
- 所有的非空節(jié)點提供2個出度和1個入度
- 所有的空節(jié)點但提供0個出度和1個入度
- 當(dāng)遍歷節(jié)點時镜粤，每次diff - 1（因為節(jié)點提供了一個入度）。
- 如果節(jié)點非#玻褪，diff + 2（因為非空節(jié)點提供了2個出度）
- 如果序列化是正確的肉渴，那么diff在任何時刻都不會小于0，并且最終結(jié)果等于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
