297. Serialize and Deserialize Binary Tree
利用preorder，多加点括号区分左右子树
# 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
"""
# preorder traversal with ()
if root is None:
return "()"
left = self.serialize(root.left)
right = self.serialize(root.right)
return "("+str(root.val)+left+right+")"
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
# strip ()
data = data[1:-1]
if data:
data_index = 0
for i in range(len(data)):
if data[i] == "(":
data_index = i
break
root = TreeNode(data[:data_index])
# find split point
count = 0
split_index = 0
for i in range(data_index, len(data)):
if data[i] == "(":
count += 1
if data[i] == ")":
count -= 1
if count == 0:
split_index = i
break
root.left = self.deserialize(data[data_index:split_index+1])
root.right = self.deserialize(data[split_index+1:])
return root
else:
return None
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
