leetcode331

 1 class Solution:
 2     def isValidSerialization(self, preorder: str) -> bool:
 3         if preorder == '#':#空树是合法的
 4             return True
 5         nodes = preorder.split(',')
 6         stack = []
 7         first_Times = True#第一次遍历
 8         n = len(nodes)
 9         i = 0
10         while i < n:
11             cur = nodes[i]
12             if len(stack) == 0:
13                 if first_Times:
14                     first_Times = False#已经开始遍历
15                 else:
16                     return False#之前已经开始遍历，并且已经清空了树，现在又有新节点，说明是在原来空节点下面出现了子节点，非法
17                 if cur == '#':
18                     return False
19                 else:
20                     stack.append(cur)
21             else:
22                 if cur == '#':
23                     if len(stack) >= 2:#栈长度大于等于2，可以向前判断是否形成新的叶子节点
24                         tag = False
25                         while len(stack) >= 2:
26                             if stack[-1] == '#' and stack[-2] != '#':#叶子节点
27                                 stack.pop(-1)
28                                 stack.pop(-1)
29                                 tag = True#清除子树，补#标记
30                             elif stack[-1] == '#' and stack[-2] == '#':
31                                 return False#连续#，错误
32                             elif stack[-1] != '#':#父节点非空，补#标记
33                                 tag = True
34                                 break
35                         if tag:#如果有补#的标记，则进行补#
36                             if len(stack) > 0:
37                                 stack.append('#')
38                     else:
39                         if stack[-1] == '#':#前面只有1个节点，而且是#，非法
40                             return False
41                         else:
42                             stack.append(cur)#前面不是#，直接添加
43                 else:
44                     stack.append(cur)#非空节点，直接添加
45             i += 1
46         return len(stack) == 0#判断栈是否可以清空，如果可以清空，则是合法的前缀序列
算法思路：栈。
各种if else，可读性极差，但是修修补补也做出来了。具体的逻辑，请看代码注释吧。