此题与jz037.序列化二叉树相同。这个算法的时间复杂度是O(N),空间复杂度是O(N)。
# 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
"""
res = []
def dfs(root):
if not root:
res.append("$")
return
res.append(root.val)
dfs(root.left)
dfs(root.right)
dfs(root)
return res
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
l = data[::-1]
def construct(val):
if val != "$":
node = TreeNode(val)
node.left = construct(l.pop())
node.right = construct(l.pop())
return node
else:
node = None
return construct(l.pop())
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
PREVIOUSjz039.数组中出现次数超过一半的数字
NEXTjz038.字符串的排列