## 题目描述：

LeetCode 449. Serialize and Deserialize BST

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

## 解题思路：

`先序遍历原始二叉树，输出逗号分隔值字符串。`

```利用栈（Stack），节点栈nstack保存重建二叉树过程中的节点，最大值栈rstack保存当前节点的右孩子允许的最大值。

记rstack的栈顶元素为rtop，当val > rtop时，执行循环：

重复弹出nstack，直到ntop不是右孩子为止（nstack[-1] > nstack[-2]条件不成立）

再次弹出nstack， 并弹出rstack

上述过程执行完毕后，令ntop.right = node，并将node压入nstack```

## Python代码：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
if not root: return ''
left = self.serialize(root.left)
right = self.serialize(root.right)
ans = str(root.val)
if left: ans += ',' + left
if right: ans += ',' + right
return ans

def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
if not data: return None
nstack, rstack = [], [0x7FFFFFFF]
for val in map(int, data.split(',')):
node = TreeNode(val)
if nstack:
if val < nstack[-1].val:
nstack[-1].left = node
rstack.append(nstack[-1].val)
else:
while val > rstack[-1]:
while nstack[-1].val > nstack[-2].val:
nstack.pop()
rstack.pop()
nstack.pop()
nstack[-1].right = node
nstack.append(node)
return nstack[0]

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
``````

Pingbacks已关闭。