leetcode-297. 二叉树的序列化与反序列化

  • English:

leetcode-297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例: 

1
2
3
4
5
6
7
8
你可以将以下二叉树:

1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"

思路: 用了简单的先序递归思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# 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
"""
ans = []
self.traverse(root, ans)
output = ''.join(ans)
return output

def traverse(self, root, ans):
if not root:
ans.append('null')
ans.append(',')
return

ans.append(str(root.val))
ans.append(',')

self.traverse(root.left, ans)
self.traverse(root.right, ans)


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

:type data: str
:rtype: TreeNode
"""
anslist = data.split(',')
return self.traversed(anslist)

def traversed(self, anslist):
if not anslist:
return None
first = anslist[0]
del anslist[0]
if first == 'null':
return None
root = TreeNode(int(first))

root.left = self.traversed(anslist)
root.right = self.traversed(anslist)

return root

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
-------The end of this article  Thank you for your reading-------
  • 本文作者: Eree
  • 本文链接: https://ereebay.me/posts/17458/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!