题目描述：

LeetCode 331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-oder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as `#`.

```     _9_
/   \
3     2
/ \   / \
4   1  #  6
/ \ / \   / \
# # # #   # #
```

For example, the above binary tree can be serialized to the string `"9,3,4,#,#,1,#,#,2,#,6,#,#"`, where `#` represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character `'#'` representing `null` pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as `"1,,3"`.

Example 1:
`"9,3,4,#,#,1,#,#,2,#,6,#,#"`
Return `true`

Example 2:
`"1,#"`
Return `false`

Example 3:
`"9,#,#,1"`
Return `false`

Python代码：

``````class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
stack = collections.deque()
for item in preorder.split(','):
stack.append(item)
while len(stack) >= 3 and \
stack[-1] == stack[-2] == '#' and \
stack[-3] != '#':
stack.pop(), stack.pop(), stack.pop()
stack.append('#')
return len(stack) == 1 and stack[0] == '#'
``````

Python代码：

``````class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
diff = 1
for item in preorder.split(','):
diff -=1
if diff < 0: return False
if item != '#': diff += 2
return diff == 0
``````

Python代码：

``````class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
items = preorder.split(',')
map = dict()
def isValid(start, end):
size = end - start + 1
if size == 0:
return False
if items[start] == '#':
return size == 1
if size == 3:
return items[start + 1] == items[start + 2] == '#'
for k in range(2, size):
left, right = (start + 1, start + k - 1), (start + k, end)
vl = map.get(left)
if vl is None:
vl = map[left] = isValid(*left)
vr = map.get(right)
if vr is None:
vr = map[right] = isValid(*right)
if vl and vr:
return True
return False
return isValid(0, len(items) - 1)
``````

Pingbacks已关闭。

1. 大睿-SCTrojan 发布于 2016年2月3日 03:22 #

我觉得第一个方法不是严格上的栈吧，毕竟栈只支持top()，这里要检查top和top的下一个以及下下一个

2. 在线疯狂 发布于 2016年2月3日 13:13 #

是的，不是严格意义上的栈，应该把栈顶的前3个元素弹出，如果不能合并，再重新压入。

3. 洪北七 发布于 2016年6月8日 14:26 #

请问第二种方法的正确性怎么理解？或者怎么证明？

4. 在线疯狂 发布于 2016年6月8日 20:42 #

我也不会严谨的证明，一个朴素的理解：如果在遍历过程中的某时刻，系统的入度>出度，则说明当前序列中出现过的所有分支节点的“空闲分支”均已用完，后序节点没有办法挂载到之前出现的节点之上。从而判定先序遍历的序列是不合法的。

5. 洪北七 发布于 2016年6月10日 09:47 #

谢谢，隐约可以理解一下。