利用栈来前序遍历二叉树序列,如果发现不能走下去了,那么序列就是无效的。
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
preorder = preorder.split(',')
stack = list()
#下边两行只是为了提前判断一些case,去掉也可以。
if preorder[-1] != '#':
return False
for index, c in enumerate(preorder):
if c != '#':
stack.append(c)
else:
if stack:
stack.pop()
else:
stack.append('#')
break
if index == len(preorder) - 1 and stack == ['#']:
return True
else:
return False