剑指61-序列化二叉树

Posted on | In |

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

  • 序列化和反序列化都用递归比较简单。特别是反序列化，能够免去回溯节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def Serialize(self, root):
        def recur(root):
            if root is None:
                return '$,'
            return str(root.val) + ',' + recur(root.left) + recur(root.right)
        return recur(root)

    def Deserialize(self, s):
        # 递归的方法可以免去回溯操作
        def recur(ss, pt):
            c = ss[pt[0]] 
            pt[0] += 1
            if c == '$':
                return None
            else:
                node = TreeNode(int(c))
                node.left = recur(ss, pt)
                node.right = recur(ss, pt)
                return node
        ss = s.split(',')[:-1] # 因为序列化之后最后一个字符是`,`，split函数分割的结果的最后一个是空字符串
        pt = [0] # 用来记录扫描ss的指针
        return recur(ss, pt)

如下是非递归版本，序列化和反序列化都是用的非递归。

  • 反序列化里花费很大功夫去确定下一个字符属于哪个节点的哪个孩子。
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
class Solution(object):
    def Serialize(self, root):
        # write code here
        s = ''
        mystack = []
        mystack.append(root)
        while len(mystack) > 0:
            node = mystack.pop(-1)
            if node is None:
                s += '$,'
                continue
            s += str(node.val) + ','
            mystack.append(node.right)
            mystack.append(node.left)
        return s 
    def Deserialize(self, s):
        # write code here
        s = s.split(',')[:-1]
        if len(s) == 0:
            return None
        if s[0] == '$':
            return None
        mylist = [] # 添加节点，或者None，与s里已经遍历的字符数相等
        mylist.append(TreeNode(int(s[0]))) 
        ix = 0 
        for char in s[1:]:
            if ix == len(mylist) - 1: # 说明左子树没有被遍历过
                if char == '$': #ix不增
                    mylist[ix].left = '$'
                    mylist.append('$')
                else: # ix加1
                    mylist[ix].left = TreeNode(int(char))
                    mylist.append(mylist[ix].left)
                    ix += 1
            else: # 左子树被遍历过，现在遍历右子树
                if char == '$':
                    mylist[ix].right = '$'
                    mylist.append('$')        
                    while ix >= 0 and not (mylist[ix] != '$' and mylist[ix].right is None):
                        ix -= 1
                else:
                    mylist[ix].right = TreeNode(int(char))
                    mylist.append(mylist[ix].right)
                    ix = len(mylist) - 1
        # 把设置的标志$都替换成None
        # 因为节点初始化的时候，其左右子树都是None，但最终的树里其左右子树不一定是None
        # 为了区分开来，就将已经确定是None的，用标志$来记录
        for node in mylist: 
            if node != '$' and node is not None:
                if node.left == '$':
                    node.left = None
                if node.right == '$':
                    node.right = None
        return mylist[0]