每天一道编程题——二叉树的序列化和反序列化

Code

二叉树被记录成文件的过程称为二叉树的序列化
同通过文件重建二叉树的过程称为二叉树的反序列化
方法一：
通过先序遍历实现序列化和反序列化
建立string，先序遍历二叉树，如果遇到null节点，就在string的末尾加上”#!”,”#”表示这个节点为空，”!”表示一个值的结束。对于不为空的节点，假设3，则为”3!”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
    self.left = left
    self.right = right
    self.value = value
def serialByPre(head):
if head == None:
    return '#!'
string = str(head.value) + '!'
string += serialByPre(head.left)
string += serialByPre(head.right)
return string
def reconByPreString(string):
l = deque(string.split('!'))
def reconPreOrder(l):
    value = l.popleft()
    if value == '#':
        return None
    head = Node(int(value))
    head.left = reconPreOrder(l)
    head.right = reconPreOrder(l)
    return head
return reconPreOrder(l)

方法二：
通过层次遍历

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
def serialByLevel(head):
if head == None:
    return '#!'
string = str(head.value) + '!'
queue = deque()
queue.append(head)
while len(queue) != 0:
    head = queue.popleft()
    if head.left is not None:
        string += str(head.left.value) + '!'
        queue.append(head.left)
    else:
        string += '#!'
    if head.right is not None:
        string += str(head.right.value) + '!'
        queue.append(head.right)
    else:
        string += '#!'
return string
def reconByLevelString(levelStr):
def generateNodeByString(val):
    return Node(int(val)) if val != '#' else None
values = levelStr.split('!')
queue = deque()
index = 0
head = Node(values[index])
index += 1
if head is not None:
    queue.append(head)
while len(queue) != 0:
    node = queue.popleft()
    node.left = generateNodeByString(values[index])
    index += 1
    node.right = generateNodeByString(values[index])
    index += 1
    if node.left is not None:
        queue.append(node.left)
    if node.right is not None:
        queue.append(node.right)
return head

本文标题:每天一道编程题——二叉树的序列化和反序列化

文章作者:Vincent Zhong

发布时间:2016-10-19, 15:35:10

最后更新:2019-07-07, 13:13:10

原始链接:https://wax8280.github.io/2016/10/19/每天一道编程题——二叉树的序列化和反序列化/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
|